1
\$\begingroup\$

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

ll n;
cin>>n;

vector<ll>vec;
vec.pb(n);

if(n==1)
{
    cout<<0<<endl<<1;
}

else
{
    while(n!=1)
    {
        if(n%3==0)
        n=n/3;
        else if(n%2==0)
        n=n/2;
        else
        n=n-1;
        
        vec.pb(n);
    }
    
    cout<<vec.size()-1<<endl;
    
    for(int i=(vec.size()-1);i>=0;i--)
    cout<<vec[i]<<" ";
}
return 0;

}

for input 96234 iam getting

15

1 2 4 5 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234

but the optimal soln is

14

1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234

i know i am going wrong at the step when 10 is converted into 5 in my code but it should convert it in to 9, Please help me,

\$\endgroup\$
2
  • \$\begingroup\$ I'm sorry, but code review is for reviewing correctly working code. If it's going wrong, then it's off topic (also, Python and Java have nothing to do with what you've posted). \$\endgroup\$ Commented Nov 15, 2020 at 23:39
  • \$\begingroup\$ i have removed the python and java tags , sorry for the mistake. \$\endgroup\$ Commented Nov 15, 2020 at 23:40

1 Answer 1

Reset to default
1
\$\begingroup\$

Edit

I realized that my distinction between bottom-top and top-bottom might have caused some confusion. Going top to bottom and bottom to top is the exact same thing, just switched the starting and end points. I just made a habit of thinking about it differently. It's an unnecessary distinction (sorry for any confusion). But the general algorithm is the same.

More detailed explanation:

Just as explained below, you can start at 96234. You check the ways to get to 96233. There is only one way (subtract 1) so it is automatically the least moves. The numbers of moves it takes is 1 + number of moves takes to get to 96234, which is 0. So you store 1 into 96233. You do the same thing for 96232, 96231...

...You get to 32078, you check the paths to get there, /3 from 96234, /2 from 64156, -1 from 32079. The paths each have moves 1, 32079, and 64156 respectively. You store the smallest into the current slot.

Eventually, you get to 1, and you compare the values stored at slots 2,2,and 3. You return the lowest one + 1.

Previous Answer

Shouldn't you be going from bottom to top? Your code is doing exactly what you're telling it to do. You check if n%2==0 first, before you ever do n=n-1. That works most of the time, but as you can see, sometimes n-1 is less moves.

You won't be able to know which is the best operation if you go from top to bottom.

Instead, you should start at 1, and calculate the least amount moves it takes to get to 2,3,4... all the way to 96234. This is still of O(n), and memory wise, it is O(n) although I think you can get it down with a trick (not sure).

\$\endgroup\$
4
  • \$\begingroup\$ Yeah i get my mistake but not able to think about logic how could i go form top to bottom ?? \$\endgroup\$ Commented Nov 16, 2020 at 7:43
  • \$\begingroup\$ Top to bottom would be more tree recursion than dp, if I'm not mistaken. since at every step you have to check potentially three options, (divide 3, divide 2, subtract 1). \$\endgroup\$ Commented Nov 16, 2020 at 7:46
  • \$\begingroup\$ is there an easy approch so i could go towars solution :-( \$\endgroup\$ Commented Nov 16, 2020 at 7:53
  • \$\begingroup\$ Please don't answer questions that are off topic, instead flag them for problems so certain members of the community can decide what to do :) \$\endgroup\$ Commented Nov 16, 2020 at 17:53

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.