Description#
You are given two positive integers x and y.
In one operation, you can do one of the four following operations:
- Divide
x by 11 if x is a multiple of 11. - Divide
x by 5 if x is a multiple of 5. - Decrement
x by 1. - Increment
x by 1.
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:
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
@cache
def dfs(x: int) -> int:
if y >= x:
return y - x
ans = x - y
ans = min(ans, x % 5 + 1 + dfs(x // 5))
ans = min(ans, 5 - x % 5 + 1 + dfs(x // 5 + 1))
ans = min(ans, x % 11 + 1 + dfs(x // 11))
ans = min(ans, 11 - x % 11 + 1 + dfs(x // 11 + 1))
return ans
return dfs(x)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
private Map<Integer, Integer> f = new HashMap<>();
private int y;
public int minimumOperationsToMakeEqual(int x, int y) {
this.y = y;
return dfs(x);
}
private int dfs(int x) {
if (y >= x) {
return y - x;
}
if (f.containsKey(x)) {
return f.get(x);
}
int ans = x - y;
int a = x % 5 + 1 + dfs(x / 5);
int b = 5 - x % 5 + 1 + dfs(x / 5 + 1);
int c = x % 11 + 1 + dfs(x / 11);
int d = 11 - x % 11 + 1 + dfs(x / 11 + 1);
ans = Math.min(ans, Math.min(a, Math.min(b, Math.min(c, d))));
f.put(x, ans);
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int minimumOperationsToMakeEqual(int x, int y) {
unordered_map<int, int> f;
function<int(int)> dfs = [&](int x) {
if (y >= x) {
return y - x;
}
if (f.count(x)) {
return f[x];
}
int a = x % 5 + 1 + dfs(x / 5);
int b = 5 - x % 5 + 1 + dfs(x / 5 + 1);
int c = x % 11 + 1 + dfs(x / 11);
int d = 11 - x % 11 + 1 + dfs(x / 11 + 1);
return f[x] = min({x - y, a, b, c, d});
};
return dfs(x);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func minimumOperationsToMakeEqual(x int, y int) int {
f := map[int]int{}
var dfs func(int) int
dfs = func(x int) int {
if y >= x {
return y - x
}
if v, ok := f[x]; ok {
return v
}
a := x%5 + 1 + dfs(x/5)
b := 5 - x%5 + 1 + dfs(x/5+1)
c := x%11 + 1 + dfs(x/11)
d := 11 - x%11 + 1 + dfs(x/11+1)
f[x] = min(x-y, a, b, c, d)
return f[x]
}
return dfs(x)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function minimumOperationsToMakeEqual(x: number, y: number): number {
const f: Map<number, number> = new Map();
const dfs = (x: number): number => {
if (y >= x) {
return y - x;
}
if (f.has(x)) {
return f.get(x)!;
}
const a = (x % 5) + 1 + dfs((x / 5) | 0);
const b = 5 - (x % 5) + 1 + dfs(((x / 5) | 0) + 1);
const c = (x % 11) + 1 + dfs((x / 11) | 0);
const d = 11 - (x % 11) + 1 + dfs(((x / 11) | 0) + 1);
const ans = Math.min(x - y, a, b, c, d);
f.set(x, ans);
return ans;
};
return dfs(x);
}
|
