Reduce N To 1

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a positive number N.
2. You have to find the minimum number of operations required to convert N into 1.
3. Operations allowed :
     (i)  If n is even, you have to replace n with n/2.
     (ii) If n is odd, you can replace n with either n-1 or n+1.
Input Format 
A number N
Output Format 
Check the sample ouput and question video.
Question Video
Constraints 
1 <= N <= 2147483647
Sample Input 
8
Sample Output 
3


  • Editorial

    The problem here deals with reducing a given number say n to 1 by performing the following operations in minimum steps:

    1. If n is even, the only operation that is allowed in this case is to divide by 2.

    2. If n is odd, both addition or subtraction by 1 is allowed.

    To understand minimization adequately, we need to understand few illustrations and so for that let us assume a number n of the form 4x + l.

    So our number can lie in one of the following { (4x + 1), (4x + 2), (4x + 3), (4x) }.

    For the cases (4x + 2) and (4x) we can only perform a single operation i.e. to divide by 2 as they are the even cases.

    Henceforth, we are only left with two cases to tackle:

    1. The number is of the form: (4x + 1)

    In this subtracting by 1 yield to minimum steps. As we can observe that by subtracting we can reach x in just 3 steps whereas by adding we can reach x in at least 4 steps. So if having x is advantageous then subtraction is effective. Now let us assume that having (x + 1) is advantageous so in that case too we can reach (x + 1) in four steps if we chose to subtract. This indicates that adding 1 to the form (4x +1) will never yield better results, so for this form, we would always subtract 1.

    2. The number is of the form: (4x + 3)

    In this case, adding 1 yield to minimum steps. As we can observe that by adding 1 we can reach (x + 1) in just 3 steps whereas by subtracting we can reach (x + 1) in at least 4 steps. So if having (x + 1) is advantageous then the addition is effective. Now let us assume that having x is advantageous so in that case too we can reach x in four steps if we chose to add. This indicates that subtracting 1 to the form (4x + 3) will never yield better results, so for this form, we would always add 1.

    Exception: 3 is the only number that does not follow this rule, can be considered as an edge case in our problem. As 3 is of the form (4x + 3) but subtracting 1 reduces it to 2 and then division makes it to 1 which is a minimized route.

     

    Time Complexity: O(logn)

    The time complexity for the function is approximately logarithmic as division by 2 is actively involved.

    Space Complexity: O(1)

    The space complexity for the function is constant.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name