# Find sequence to a target number using restricted set of primitive operations

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?

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

# 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!, ....]