# Reduce N To 1 #### 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.

• Related Topics

Run

Run
Id Name