7
\$\begingroup\$

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 <iostream>
#include <climits>
#include <vector>
#include <list>
void primitive_calculator(int64_t number)
{
        std::vector<int64_t> min_steps(number+1,INT_MAX);
        std::list<int64_t>* path=new std::list<int64_t>[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;i++)
        {
            if(i%3==0)
            {
                if(min_steps[i/3] < 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] < 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] < min_steps[i])
            {
                min_steps[i]=min_steps[i-1]+1;
                path[i]=path[i-1];
                path[i].push_back(i);
            }
    }
    std::cout<<min_steps[number]<<"\n";
    while(!path[number].empty())
    {
            std::cout<<path[number].front()<<" ";
            path[number].pop_front();
    }
}
int main()
{
    int64_t number;
    std::cin>>number;
    primitive_calculator(number);
    return 0;
}
\$\endgroup\$
6
\$\begingroup\$

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<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  << " ";
    }
}

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";
\$\endgroup\$
  • \$\begingroup\$ How did you calculate execution time? \$\endgroup\$ – A.Gautam Sep 7 '16 at 10:18
  • \$\begingroup\$ @A.Gautam: See update. \$\endgroup\$ – Martin R Sep 7 '16 at 11:08
2
\$\begingroup\$
void primitive_calculator(int64_t number)
{
        std::vector<int64_t> min_steps(number+1,INT_MAX);
        std::list<int64_t>* path=new std::list<int64_t>[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;i++)
        {
            if(i%3==0)
            {
                if(min_steps[i/3] < 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] < 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] < min_steps[i])
            {
                min_steps[i]=min_steps[i-1]+1;
                path[i]=path[i-1];
                path[i].push_back(i);
            }
    }
    std::cout<<min_steps[number]<<"\n";
    while(!path[number].empty())
    {
            std::cout<<path[number].front()<<" ";
            path[number].pop_front();
    }
}

Even assuming you needed to maintain the path list, this isn't the most efficient way to do so. Consider

void primitive_calculator(int32_t number)
{
    std::list<int32_t>* path = new std::list<int32_t>[number+1];

    path[1].push_back(1);

    for (int i = 2; i <= number; i++)
    {
        std::size_t previous = i - 1;

        if ((i%3 == 0) && (path[i/3].size() < path[previous].size()))
        {
            previous = i/3;
        }

        if ((i%2 == 0) && (path[i/2].size() < path[previous].size()))
        {
            previous = i/2;
        }

        path[i] = path[previous];
        path[i].push_back(i);
    }

    std::cout << path[number].size() - 1 << '\n';
    while (!path[number].empty())
    {
        std::cout << path[number].front() << ' ';
        path[number].pop_front();
    }
}

This saves allocating and initializing the min_steps vector. Instead, it assumes that the choice is going to be to subtract one and uses that as the basis for comparison. This works because you can always subtract one. The size of the path list is one more than the value that we want, but so long as we compare consistent values, it works.

Your original version could copy the path list up to three times per iteration. This version will only copy once. And only insert once.

I switched from int64_t to int32_t because thirty-one bits is plenty to hold a number as high as two billion, much less a million. And this should use less space (assuming the compiler doesn't optimize by promoting 32 bits to 64 or more bits for some reason).

This is not to say that this version is the most efficient. It's not. Saving the fewest steps and the previous number is going to be more space efficient and likely more time efficient. It is more efficient than your version though.

For better separation of concerns, consider returning path[number] rather than displaying output in this function. Then you can do the display elsewhere. That won't matter for this problem, but it is a good habit for other problems. It essentially makes the function more useful.

I'd prefer a different name for this function, e.g. find_shortest_path or calculate_fewest_steps. As a rule of thumb, functions should have verb names. They do things. I would expect a primitive_calculator to be some kind of object, as nouns denote objects. They are things. Also, primitive_calculator doesn't tell me much about what you are calculating.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.