2
\$\begingroup\$

Given an integer 𝑛, compute the minimum number of operations(+1, x2, x3) needed to obtain the number 𝑛 starting from the number 1.

I did this using this code:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> v(n+1, 0);
    v[1] = 1;
    for(int i = 1; i < v.size(); i++)
    {
        if((v[i + 1] == 0) || (v[i + 1] > v[i] + 1))
        {
            v[i + 1] = v[i] + 1;
        }
        if((2*i <= n) && (v[2*i] == 0 || v[2*i] > v[i] + 1))
        {
            v[2*i] = v[i] + 1;
        }
        if((3*i <= n) && (v[3*i] == 0 || v[3*i] > v[i] + 1))
        {
            v[3*i] = v[i] + 1;
        }
    }
    cout << v[n] - 1 << endl;
    vector<int> solution;
    while(n > 1)
    {
        solution.push_back(n);
        if(v[n - 1] == v[n] - 1)
        {
            n = n-1;
        }
        else if(n%2 == 0 && v[n/2] == v[n] - 1)
        {
            n = n/2;
        }
        else if(n%3 == 0 && v[n/3] == v[n] - 1)
        {
            n = n/3;
        }
    }
    solution.push_back(1);
    reverse(solution.begin(), solution.end());
    for(size_t k = 0; k < solution.size(); k++)
    {
        cout << solution[k] << ' ';
    }
}

Input:

5

Output:

3
1 2 4 5

Do you have any optimized way to do this?

\$\endgroup\$
  • 1
    \$\begingroup\$ The algorithm looks good already. What clue make you think it is possible to improve it ? Bad performance on a competitive site ? \$\endgroup\$ – Damien Jul 8 at 19:04
  • \$\begingroup\$ @Damien yes exactly, the grader is not accepting it! \$\endgroup\$ – baapcoder_ Jul 9 at 10:59
3
\$\begingroup\$

using namespace std;

Stop doing this. It is a easy, but sloppy, way to code; a change to the standard library that introduces a new identifier can break your code.

Being explicit, and writing std::vector instead of vector everywhere would be painful. But there is a middle ground:

#include <vector>
using std::vector;

Now you can lazily use vector, without fear that something you are not using from the standard library will suddenly become defined, colliding with your identifiers, and causing carnage.

White space

Either put white space around all binary operators, like v[i + 1], or never put the white space around the binary operators, like v[i*2]. But be consistent.

cout << endl;

Don't use this; it slows your code down. The endl manipulator does two things: it adds \n to the stream AND it flushes the stream. If you don't need to flush the stream (and you rarely do), simply write

cout << '\n';

Avoid repeated calls to functions that return the same result

for(int i = 1; i < v.size(); i++)

What is the value of v.size()? Will it ever change? Can the compiler tell it won't, and optimize it out? Could you store the value in a local variable to avoid the repeated function calls?

Or ... you could use the variable that already exists: n.

for(int i = 1; i <= n; i++)

Don't Repeat Yourself (DRY)

        if((v[i + 1] == 0) || (v[i + 1] > v[i] + 1))
        {
            v[i + 1] = v[i] + 1;
        }
        if((2*i <= n) && (v[2*i] == 0 || v[2*i] > v[i] + 1))
        {
            v[2*i] = v[i] + 1;
        }
        if((3*i <= n) && (v[3*i] == 0 || v[3*i] > v[i] + 1))
        {
            v[3*i] = v[i] + 1;
        }

These statements look very similar.

        if((target <= n) && (v[target] == 0 || v[target] > v[i] + 1))
        {
            v[target] = v[i] + 1;
        }

You could pull them out into a function:

inline void explore_step(vector<int> &v, int n, int i, int target) {
    if ((target <= n) && (v[target] == 0 || v[target] > v[i] + 1)) {
        v[target] = v[i] + 1;
    }
}

And then write:

        explore_step(v, n, i, i+1);
        explore_step(v, n, i, i*2);
        explore_step(v, n, i, i*3);

Optimization

You approach takes \$O(n)\$ time, because you explore each value from 1 to n.

You do this, because you don't know which values are going to be useful in reaching the target value, and test things like v[2*i] > v[i] + 1 because you don't know which values could be reached via a faster path.

A slightly better approach:

  • seed 1 into a list of values to explore
  • for each value in the list of values to explore:
    • for each of the 3 target values i+1, i*2, & i*3 if <= n:
      • if v[target] == 0, then
        • store v[target] = i
        • add target to the list of values to explore
        • if target == n, stop

Consider n = 10.

explore = [1], value = 1, targets = [2, -, 3]
explore = [1, 2, 3], value = 2, targets = [-, 4, 6]
explore = [1, 2, 3, 4, 6], value = 3, targets = [-, -, 9]
explore = [1, 2, 3, 4, 6, 9], value = 4, targets = [5, 8, -]
explore = [1, 2, 3, 4, 6, 9, 5, 8], value = 6, targets = [7, -, -]
explore = [1, 2, 3, 4, 6, 9, 5, 8, 7], value = 9, targets = [10, -, -]

You could use a queue for explore, but a vector of length n, and just walking forward through the items works fine.

Notice that all values reachable after 1 step [2, 3] are processed before values reachable after 2 steps [4, 6, 9], and would be processed before those values reachable after 3 steps [5, 8, 7], and so on.

More over, we've built up a trail of breadcrumbs for the fastest path.

v[10] = 9
v[9] = 3
v[3] = 1

So no searching is required to find the correct path.

Implementation left to student.


Can we do better? What if we started with n, and explored n-1, n/2, and n/3? An odd value can't lead to an n/2 point, and a non-multiple-of-3 can't lead to a n/3 point, so you may be pruning more values out of the search, so might be slightly faster.

[28] -> [27, 14]
     -> [26, 9, 13, 7]
     -> [25, 13, 8, 3, 12, 6]
     -> [24, 12, 4, 2, 1!, ....]
| improve this answer | |
\$\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.