Experience is the name everyone gives to their mistakes. Oscar Wilde
Reduce N to 1
Introduction: Welcome back, dear reader. So, how is it going? We hope that you are
enjoying these problems on bit manipulation. So, let's start with the discussion on this problem
called REDUCE N TO 1.. So, what does this question say? We are given a
number N and we have to reduce it to 1 by performing a minimum number of operations. Also, if the
given number is even, we can perform only one operation and that is divide the number by 2. If the
number is odd, we can perform 2 operations on it i.e. add 1 to the number or subtract 1 from the
number. Some of the examples are given below:
So, dear reader, as you can see in the image shown above, the number 5 can be reduced to 1 in 5
steps, 4 steps and even 3 steps also. So, the minimum number of operations required to reduce 5 to 1
are 3. So, our output will also be 3. Similarly, 4 can be reduced only in 2 operations and there is
no other possibility for it. So, the answer for 4 is 2. Also, the answer for 6 is 3.
We hope that you have understood the question completely. You may refer to the REDUCE N TO 1 VIDEO
(0:00-1:12) to understand the question completely and resolve your doubts about the question if any.
We recommend you try to solve the problem on your own first and then refer to the solution.
Time Complexity: Complexity: O(log2n) where n is the input number. Space Complexity: O(1)
Explanation:
Dear reader, we would like to concentrate completely on the article now as this is going to be very
interesting and conceptual too. So, we know that in the case of an even number, we keep dividing the
number by two. So, it is a simple case.
But, when the number is an odd number or when we divide an even number by two and then it becomes an
odd number then also, it is not clear to us till now what we should do. Should we perform the minus
operation or the plus operation when the number is an odd number? Let us take two odd numbers and
see what conclusions we can draw from them but before that, we want you to understand a very basic
thing.
The numbers represented by (2x+1) are the odd numbers and the numbers represented by (2x) are the
even numbers. This is something that you already know. Now, let us see one more representation. The
numbers represented by (4x) and (4x+2) are even numbers and the numbers represented by (4x+1) and
(4x+3) are odd numbers. Why? Think!!! (This is basic mathematics).
So, we can now say that the even numbers are of two types and those are (4x) and (4x+2) and the odd
numbers are also of two types and those are (4x+1) and (4x+3). Now that you have an idea of this
concept, let us take two odd numbers and see the minimum number of operations required to turn them
into 1.
As you can see in the image above, we took a number 4n+1= 4(1)+1=5 and this number was reduced to 1
in the minimum number of operations when we performed the subtraction operation at the beginning.
Now let us take another number which is of the type, 4n+3.
Now as you can see, the number 15 which is of the type (4x+3) gave us the result as 1 in the minimum
number of 5 operations when we started by addition operation initially.
So, this is the case for all the odd numbers. If a number is of the type 4x+1, it will
reduce to 1
in minimum number of operations when we do the minus operation at the beginning and the number
of
the type (4x+3) will be reduced to 1 in minimum number of operations when we perform addition
operation initially.
Also, there is an exception in the above case. The number 3 is of the type 4n+3 where n=0 but it
reduces to 1 in the minimum number of operations when we perform subtraction initially rather
than naddition which gives the minimum number of operations in all the other numbers of type
4n+3.
So, now we know which kind of number will give us the minimum number of operations on doing what
operation. But, we know that you are curious to know how exactly we come to the above conclusion
about the two types of odd numbers.
So, let us do a proof that will definitely clear your thinking and mind regarding this concept. So,
first let us take a number of type 4x+1. Since it is an odd number, we can perform two operations
initially and those are adding or subtracting 1. These are as shown below:
After adding 1 or subtracting 1 from the number, we get both the even numbers. One is the number
4x+2 and the other is the number 4x. See, the case for 4x is simple. It will just get divided by 2
till we reach x.
Now, the number 4x+2 will also be divided by 2 and it gives the answer 2x+1 which is again an odd
number.
Again, 2x+1 is an odd number and it has both the options of adding or subtracting 1. If we add 1 we
get 2x+2 and if we subtract 1, we get 2x. 2x will be reduced to x and 2x+2 will be reduced to x+1.
Now, we can see that we have reached a state from where we cannot break down this tree further. So,
we don't know whether x or x+1 will take minimum operations to reach 1. Let us assume that x takes
minimum operations to reach 1. So, in the tree above, we can reach x in less number of operations if
we used the minus operation at the beginning. So, the minus operation seems to be providing us with
less number of operations.
Now, if we assume that x+1 takes less number of operations to reach 1 as compared to x then we will
have to first see that x+1 only comes when we do addition initially. So, x+1 has occurred after 4
operations. Now, if you see on the other slide, we have the values till x. If we want to make it x+1
since it takes less number of operations to 1 then we will add 1 to x i.e. one more operation will
be performed.
Now, when x+1 takes less operations, we reach x+1 in equal numbers of operations whether we add at
the beginning or we subtract at the beginning but if x takes more operations, we have already
concluded that subtracting in the beginning is better. So, we can conclude that when the number is
of the type (4x+1) then it is always better to choose the minus operation.
So, we have proved why we said that when the number is of the form 4x+1, it is always better to
subtract. Similarly, you can prove by yourself that whenever we have a number of the form 4x+3, iit
is better to perform the addition operation.
We recommend you try to draw the tree diagram and prove it yourself. The tree diagram will be as shown
in the figure below:
We recommend you refer to the solution video to understand the entire procedure and
concept explained above.
Algorithm:
If the given number is an even number, divide it by 2 i.e. n=n/2.
If it is of the form 4x+3, perform the addition operation i.e. n=n+1.
If it is of the form 4x+1, perform the subtraction operation i.e. n=n-1.
Increment the count of operations by 1 whenever you perform any one of the above operations.
Continue this procedure till we get n=1.
Now that we have understood the complete procedure, let us write the code for the same.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
System.out.println(solution(n));
}
public static int solution(long n) {
int res=0;
while(n!=1)
{
if(n%2==0)
{
n=n/2;
}
else if(n==3)
{
res=2;
break;
}
else if((n&3)==1)
{
n=n-1;
}
else if((n&3)==3)
{
n=n+1;
}
res++;
}
return res;
}
}
java;
true";
The above code is written and explained in the solution video . You may refer to it to
understand the code and clear all your doubts about it. Now let us discuss the time and space
complexity of the above solution.
Time and Space Complexity Analysis
Time Complexity: The time complexity of the above solution is O(log2n).
This is because we
usually keep dividing the number by 2 until we obtain onne. For instance, we can reduce 16
to 1 in just 4 operations. Why 4? Calculate log216=4. So, the time complexity is O(log2n)
where n is the input number given to us.
Space Complexity: The space complexity of the above solution is O(1) as we
have not used any extra space for solving this problem.
So, dear reader, we hope that you have understood the problem completely. If you have any
doubts regarding this problem, we suggest you refer to the complete solution video for the
same. With this, we have completed this problem.
Suggestions:
Here are some suggestions from our side that you do not want to miss:
We highly recommend you watch the solution video . This is the explanation of
the code. This part of the solution video will make your understanding a lot stronger and
also you will see such a corner test case that you might have not thought about. So, have a
look at it. Till then, Happy Coding!!!
