2998. Minimum Number of Operations to Make X and Y Equal
Medium48.4% acceptance27,912 / 57,620 submissions
Asked by 2 companies
Topics
You are given two positive integers x and y.
In one operation, you can do one of the four following operations:
- Divide
xby11ifxis a multiple of11. - Divide
xby5ifxis a multiple of5. - Decrement
xby1. - Increment
xby1.
Return the minimum number of operations required to make x and y equal.
Example 1:
Input: x = 26, y = 1 Output: 3 Explanation: We can make 26 equal to 1 by applying the following operations: 1. Decrement x by 1 2. Divide x by 5 3. Divide x by 5 It can be shown that 3 is the minimum number of operations required to make 26 equal to 1.
Example 2:
Input: x = 54, y = 2 Output: 4 Explanation: We can make 54 equal to 2 by applying the following operations: 1. Increment x by 1 2. Divide x by 11 3. Divide x by 5 4. Increment x by 1 It can be shown that 4 is the minimum number of operations required to make 54 equal to 2.
Example 3:
Input: x = 25, y = 30 Output: 5 Explanation: We can make 25 equal to 30 by applying the following operations: 1. Increment x by 1 2. Increment x by 1 3. Increment x by 1 4. Increment x by 1 5. Increment x by 1 It can be shown that 5 is the minimum number of operations required to make 25 equal to 30.
Constraints:
1 <= x, y <= 104
Hints
Hint 1
The only way to make
x larger is to increase it by 1 so if y >= x the answer is y - x.Hint 2
For
y < x, x - y is always a candidate answer since we can repeatedly decrease x by one to reach y.Hint 3
We can also increase
x and then use the division operations. For example, if x = 10 and y = 1, we can increment x by 1 then divide it by 11.Hint 4
Find an upper bound
U on the maximum value of x we will reach an optimal solution. Since all values of x will be in the range [1, U], we can use BFS to find the answer.Hint 5
One possible upper bound on
x is U = x + (x - y) . To reach any number strictly greater than U from x, we will need more than x - y operations which is not optimal since we can always reach y in x - y operations.