Obtaining a target number only using the operations ×2, ×3, and +1 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 &lt;=n &lt;= 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 &lt;iostream&gt;
#include &lt;climits&gt;
#include &lt;vector&gt;
#include &lt;list&gt;
void primitive_calculator(int64_t number)
{
        std::vector&lt;int64_t&gt; min_steps(number+1,INT_MAX);
        std::list&lt;int64_t&gt;* path=new std::list&lt;int64_t&gt;[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&lt;=number;i++)
        {
            if(i%3==0)
            {
                if(min_steps[i/3] &lt; min_steps[i])
                {
                        min_steps[i]=min_steps[i/3]+1;
                        path[i]=path[i/3];
                        path[i].push_back(i);
                }
            }
            if(i%2==0)
            {
                if( min_steps[i/2] &lt; min_steps[i])
                {
                        min_steps[i]=min_steps[i/2]+1;
                        path[i]=path[i/2];
                        path[i].push_back(i);
                }
            }
            if( min_steps[i-1] &lt; min_steps[i])
            {
                min_steps[i]=min_steps[i-1]+1;
                path[i]=path[i-1];
                path[i].push_back(i);
            }
    }
    std::cout&lt;&lt;min_steps[number]&lt;&lt;"\n";
    while(!path[number].empty())
    {
            std::cout&lt;&lt;path[number].front()&lt;&lt;" ";
            path[number].pop_front();
    }
}
int main()
{
    int64_t number;
    std::cin&gt;&gt;number;
    primitive_calculator(number);
    return 0;
}
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&lt;int32_t&gt; min_steps(number + 1);
    std::vector&lt;int32_t&gt; predecessor(number + 1);

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


    std::cout &lt;&lt; min_steps[number] &lt;&lt; "\n";

    std::list&lt;int32_t&gt; 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 &lt;&lt; *it  &lt;&lt; " ";
    }
}


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 &lt;&lt; "\ntime: " &lt;&lt; float( end_time - begin_time ) /  CLOCKS_PER_SEC &lt;&lt; "\n";