Prerequisite : Basic math, Bitset, Bruteforce
Problem statement summary : You are given two inetegers A and B (A<=B) and you need to find out minimum number of operations requried to make A equal to B.
In one operations you can do one of the following
A=A+1 (increase A by 1)
or
A=A∗2 (multiply A by 2)
Solution : We need to minimize the adding operations.
Let’s see an example, Suppose A =2 and B =15,
1st Observation :
Operation 1 : A = A * 2 = 4
Operation 2: A = A * 2 = 8
A = A+(7 times increasing )= 8 + 7 = 15 , because if we multiple by 2 then A = 16 which is greater than B.
So total operation: 2 + 7 = 9.
2nd Observation :
If we do same things by reversely from B and instead of adding we can subtract and, instead of multiple we can divide by 2.
Operation 1 : B = B -1 = 15-1 =14 (we cannot divide by 2, because B =15, is odd).
Operation 2 : B = B/2 = 7 (B=14 is even, we can divide by 2).
Operation 3: B= B-1= 6
Operation 4 : B =B/2 = 3
Operation 5 : B = B-1 = 2==A.
So total operation : 5, which is minimum.
We can clearly see that , 2nd observation is the efficient approach .
Time Complexity : O (2 * log ( B - A) );