3. Min Steps to 1 #

Created Monday 09 March 2020

Given a positive integer n, find the minimum number of steps s, that takes n to 1. You can perform any one of the following 3 steps.

1.) Subtract 1 from it. (n= n - ­1) , 2.) If its divisible by 2, divide by 2.( if n%2==0, then n= n/2 ) , 3.) If its divisible by 3, divide by 3. (if n%3 == 0, then n = n / 3 ).

WAP to do this. note: The idea that 3 divides in the most basic parts, then divide by 2 then -1. This is **wrong, **as seen from a simple case of 10. This is because we do not know the factors of the numbers.

Soln: We follow the three steps to get to DP.

1. Bruteforce
   1. If n is 1 return 0, no steps required.
   2. Init n1 = n, n2 = n, n3 = n. This is the maximum value n1, n2 and n3 can have. So that there’s no need for INT_MAX and minimum function can be handled easily.
   3. If n%2==0, n1 = f(n/2) + 1; // counting this step
   4. 2 and n3If n%3==0, n2 = f(n/3) +1; // counting this step
   5. n3 = f(n-1) + 1;
   6. return minimum(n1, n2, n3);
2. Memoization - top down approach

• We make an array for storing the primitive cases.
• The size of the array is n+1. Initialize to all to -1. Except for (n=1, val=0).
• Write a recursive solution.

3. DP bottom up solution

• We try to make all solutions which are from the concrete ones.
• So for each number, we write the value 1 + f(i) at i+1, i2 and i3. But only if the values there are greater than the value we are going to write(i.e 1 + f(i)). This is because we want the least value for every node.
• We cannot exit if we have got a value of f(n) as we need the minimum.
• For each number, as the answer can include any of the numbers less than it.(This is true for all n), hence we need to take the minimum of all the values that are written.

Proof:

• As concrete values are a minimum, they will generate the values(acc to the rules), which will be given to the targets.

• Now some other value may become the source for the chain to the same node later on(i.e by some bigger node, proved by observation).

• If this is less than the value for the previous it will be replaced. This is generalizable to any number of collisions(because we are finding the minimum). Hence the whole process will be required for producing f(n).

• This finding the minimum is done implicitly, i.e it will happen as concreteness increases.

• Hence we will generate concrete steps forward. And by similar progression f(n) will be made concrete. This process will end after n iterations with all the loops.

• T.C = O(rules*n)