Skip to content

2998. Minimum Number of Operations to Make X and Y Equal 👍

  • Time: $O(\max(x, y))$
  • Space: $O(\max(x, y))$
 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
27
28
29
30
class Solution {
 public:
  int minimumOperationsToMakeEqual(int x, int y) {
    if (x <= y)
      return y - x;

    queue<int> q{{x}};
    unordered_set<int> seen;

    for (int ans = 0; !q.empty(); ++ans) {
      for (int sz = q.size(); sz > 0; --sz) {
        const int num = q.front();
        q.pop();
        if (num == y)
          return ans;
        if (seen.find(num) != seen.end())
          continue;
        seen.insert(num);
        if (num % 11 == 0)
          q.push(num / 11);
        if (num % 5 == 0)
          q.push(num / 5);
        q.push(num - 1);
        q.push(num + 1);
      }
    }

    throw;
  }
};

 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
27
28
class Solution {
  public int minimumOperationsToMakeEqual(int x, int y) {
    if (x <= y)
      return y - x;

    Queue<Integer> q = new ArrayDeque<>(List.of(x));
    Set<Integer> seen = new HashSet<>();

    for (int ans = 0; !q.isEmpty(); ++ans) {
      for (int sz = q.size(); sz > 0; --sz) {
        final int num = q.poll();
        if (num == y)
          return ans;
        if (seen.contains(num))
          continue;
        seen.add(num);
        if (num % 11 == 0)
          q.offer(num / 11);
        if (num % 5 == 0)
          q.offer(num / 5);
        q.offer(num - 1);
        q.offer(num + 1);
      }
    }

    throw new IllegalArgumentException();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def minimumOperationsToMakeEqual(self, x, y):
    if x <= y:
      return y - x

    queue = collections.deque([x])
    seen = set()

    ans = 0
    while queue:
      for _ in range(len(queue)):
        num = queue.popleft()
        if num == y:
          return ans
        if num in seen:
          continue
        seen.add(num)
        if num % 11 == 0:
          queue.append(num // 11)
        if num % 5 == 0:
          queue.append(num // 5)
        queue.append(num - 1)
        queue.append(num + 1)
      ans += 1