Given a number n and 3 different operations that you can perform: n = n/2 n = n/

Question

Given a number n and 3 different operations that you can perform:

n = n/2
n = n/3
n = n?1

Give an algorithm that reaches n == 1 in the minimum number of operations for any given starting n.

Note that n/2 and n/3 compute floating point division, not integer division

[8 points] Algorithm: Your algorithm generally has a correct idea and has a polynomial runtime

[5 points] Correctness Proof: Your algorithm is correct on all inputs, has a polynomial runtime, and your proof of correctness is logically sound and complete

[2 points] Runtime Analysis: Your algorithm has a polynomial runtime and you correctly analyzed the runtime of your algorithm

Explanation / Answer

Hello student!

I am happy to help you!

The number of operations that can be used for reaching. The 1st step to the nth

Now, we can say that reaching from 1 to n takes equal steps to reach from n to 1. Is it correct?

Yes! How? The steps taken would always be the same.

Now, coming over to the algorithmic part.. We can design the algorithm as follows.

We will make a dp table of size n

dp[n+1]

for i = 0 to n

dp[i] = 0;

dp[1] = 1;

for i = 2 to n

int ans = dp[i-1]; // The minimum number of step to reach ith step is i-1

if (i%2 == 0) {

ans = min ( ans, dp[i/2] ) ; // n/2 the step minimum number

}else {

ans = min (ans, dp[floor(i/2)]+1) ; // n/2th step +1 it will reach

}

if (i%3 == 0) {

ans = min ( ans, dp[i/3] ) ; // n/3 the step minimum number

}else if (i%3 == 2){

ans = min (ans, dp[floor(i/3)]+2) ; // n/3th step +2 it will reach

}else {

ans = min (ans, dp[floor(i/3)]+1) ; // n/3th step +1 it will reach

}

dp[i] = ans;

}

return dp[n];

The algorithm has the run-time compexity of O(n) and space complexity of O(n) as well.

The following algorithm will have correct values for all input value how? We have handled the case for the steps that cannot directly reach by 2 or 3. So, we took its modulo and then reached there. It will take care of all the test cases.

Our algorithm has a single loop which runs from 1 to n and there is no recursive statement in it, It will run for O(n) in worst case.

Thank you. Feel free to ask anything. If you like the answer. Please upvote it. It means a lot. Thank you again.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.