Skip to content

2059. Minimum Operations to Convert Number 👍

  • Time: $O(1000n)$
  • Space: $O(1000)$
 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 {
 public:
  int minimumOperations(vector<int>& nums, int start, int goal) {
    queue<int> q{{start}};
    vector<bool> seen(1001);
    seen[start] = true;

    for (int step = 1; !q.empty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        const int x = q.front();
        q.pop();
        for (const int num : nums) {
          for (const int res : {x + num, x - num, x ^ num}) {
            if (res == goal)
              return step;
            if (res < 0 || res > 1000 || seen[res])
              continue;
            seen[res] = true;
            q.push(res);
          }
        }
      }

    return -1;
  }
};

 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 {
  public int minimumOperations(int[] nums, int start, int goal) {
    Queue<Integer> q = new ArrayDeque<>(List.of(start));
    boolean[] seen = new boolean[1001];
    seen[start] = true;

    for (int step = 1; !q.isEmpty(); ++step)
      for (int sz = q.size(); sz > 0; --sz) {
        final int x = q.poll();
        for (final int num : nums) {
          for (final int res : new int[] {x + num, x - num, x ^ num}) {
            if (res == goal)
              return step;
            if (res < 0 || res > 1000 || seen[res])
              continue;
            seen[res] = true;
            q.offer(res);
          }
        }
      }

    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def minimumOperations(self, nums: list[int], start: int, goal: int) -> int:
    q = collections.deque([start])
    seen = {start}

    step = 1
    while q:
      for _ in range(len(q)):
        x = q.popleft()
        for num in nums:
          for res in (x + num, x - num, x ^ num):
            if res == goal:
              return step
            if res < 0 or res > 1000 or res in seen:
              continue
            seen.add(res)
            q.append(res)
      step += 1

    return -1