- Add or multiple
- 2024-03-29 11:07:20 @

**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) );

# 0 comments

# Information

- ID
- 1044
- Difficulty
- 9
- Category
- Beginners Click to Show
- Tags
- (None)
- # Submissions
- 7
- Accepted
- 6
- Accepted Ratio
- 86%
- Uploaded By