patterncppMinor

Obtaining a target number only using the operations ×2, ×3, and +1

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

obtainingnumbertargettheoperationsusingandonly

Problem

Problem Introduction

You are given a primitive calculator that can perform the following
three operations with the current number x: multiply x by 2, multiply
x by 3, or add 1 to x. Your goal is given a positive integer n, find
the minimum number of operations needed to obtain the number n
starting from the number 1.

Task: Given an integer n, compute the minimum number of operations needed to obtain the number n starting from the number 1.

Input Format: The input consists of a single integer \$1 <=n <= 10^6.\$

Output: Print the sequence of intermediate numbers. For example for input \$ n=96234\$, output is 1 3 9 10 11 22 66 198 594 1782 5346
16038 16039 32078 96234 or 1 3 9 10 11 33 99 297 891 2673 8019 16038
16039 48117 96234. Both are valid output.

Now I have designed an algorithm and am finding intermediate numbers for each and every number between 1 and n. It is giving me time limit exceeded error. How can I improve its efficiency?

#include 
#include 
#include 
#include 
void primitive_calculator(int64_t number)
{
        std::vector min_steps(number+1,INT_MAX);
        std::list* path=new std::list[number+1];
        min_steps[0]=0; min_steps[1]=0;
        path[0].push_back(0);
        path[1].push_back(1);
        for(int i=2;i>number;
    primitive_calculator(number);
    return 0;
}

Solution

For each i = 0...number, your method stores a std::list containing
the complete sequence of intermediate numbers from 1 to i. Each list is created by
copying the list from the optimal predecessor and appending i.
Even for a single i, path[i] may be assigned a new list up to
three times.

That is a lot of copying which consumes a lot of time.
It can be improved by choosing a different data structure:
For each number, store only the "optimal predecessor".
This requires less memory and less copying.
For the final number,
the sequence of intermediate numbers can then be reconstructed by traversing the predecessors from number to 1, and printing
the numbers in reverse order.

More remarks:

The use of integer types is not consistent. You use int64_t

at most places, but int i as the loop variable, and
INT_MAX as initial value. –
For n in the given range 1...10^6, int32_t is sufficiently large.

The initialization of all elements in min_steps to INT_MAX

can be avoided by testing i - 1 as predecessor first.

Coding style: There should be more space around operators

and keywords.

The function then would look like this:

void primitive_calculator(int32_t number)
{
    std::vector min_steps(number + 1);
    std::vector predecessor(number + 1);

    for (int32_t i = 2; i  sequence;
    for (int32_t i = number; i != 0; i = predecessor[i]) {
        sequence.push_front(i);
    }
    for (auto it = sequence.begin(); it != sequence.end(); ++it) {
        std::cout << *it  << " ";
    }
}

For number = 96234, this reduced the execution time
from 0.13 seconds with your code to about 0.001 seconds.

The measurement was done on a MacBook with this simple code:

int32_t number = 96234;
const clock_t begin_time = clock();
primitive_calculator(number);
const clock_t end_time = clock();
std::cout << "\ntime: " << float( end_time - begin_time ) /  CLOCKS_PER_SEC << "\n";

Code Snippets

void primitive_calculator(int32_t number)
{
    std::vector<int32_t> min_steps(number + 1);
    std::vector<int32_t> predecessor(number + 1);

    for (int32_t i = 2; i <= number; i++) {
        min_steps[i] = min_steps[i-1] + 1;
        predecessor[i] = i - 1;
        if (i % 3 == 0) {
            if (min_steps[i/3] < min_steps[i]) {
                min_steps[i] = min_steps[i/3] + 1;
                predecessor[i] = i/3;
            }
        }
        if (i % 2 == 0) {
            if (min_steps[i/2] < min_steps[i]) {
                min_steps[i] = min_steps[i/2] + 1;
                predecessor[i] = i/2;
            }
        }
    }


    std::cout << min_steps[number] << "\n";

    std::list<int32_t> sequence;
    for (int32_t i = number; i != 0; i = predecessor[i]) {
        sequence.push_front(i);
    }
    for (auto it = sequence.begin(); it != sequence.end(); ++it) {
        std::cout << *it  << " ";
    }
}

int32_t number = 96234;
const clock_t begin_time = clock();
primitive_calculator(number);
const clock_t end_time = clock();
std::cout << "\ntime: " << float( end_time - begin_time ) /  CLOCKS_PER_SEC << "\n";

Context

StackExchange Code Review Q#140571, answer score: 7

Revisions (0)

No revisions yet.