Question

2998. 使 X 和 Y 相等的最少操作次数

English Version

题目描述

给你两个正整数 x 和 y 。

一次操作中，你可以执行以下四种操作之一：

1. 如果 x 是 11 的倍数，将 x 除以 11 。
2. 如果 x 是 5 的倍数，将 x 除以 5 。
3. 将 x 减 1 。
4. 将 x 加 1 。

请你返回让 x 和 y 相等的 最少 操作次数。

 

示例 1：

输入：x = 26, y = 1
输出：3
解释：我们可以通过以下操作将 26 变为 1 ：
1. 将 x 减 1
2. 将 x 除以 5
3. 将 x 除以 5
将 26 变为 1 最少需要 3 次操作。

示例 2：

输入：x = 54, y = 2
输出：4
解释：我们可以通过以下操作将 54 变为 2 ：
1. 将 x 加 1
2. 将 x 除以 11
3. 将 x 除以 5
4. 将 x 加 1
将 54 变为 2 最少需要 4 次操作。

示例 3：

输入：x = 25, y = 30
输出：5
解释：我们可以通过以下操作将 25 变为 30 ：
1. 将 x 加 1
2. 将 x 加 1
3. 将 x 加 1
4. 将 x 加 1
5. 将 x 加 1
将 25 变为 30 最少需要 5 次操作。

 

提示：

• 1 <= x, y <= 104

解法

方法一

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)

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;
  }
}

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

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)
}

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