Reduce N To 1
1. You are given a positive number N.Input Format
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.
A number NOutput Format
Check the sample ouput and question video.Question Video
1 <= N <= 2147483647Sample Input
8Sample 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