Leetcode

Minimum Operations to Convert Number

  • Time:O(1000n)
  • Space:O(1000)

C++

class Solution {
 public:
  int minimumOperations(vector<int>& nums, int start, int goal) {
    int ans = 0;
    queue<int> q{{start}};
    vector<bool> seen(1001);
    seen[start] = true;

    while (!q.empty()) {
      ++ans;
      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 ans;
            if (res < 0 || res > 1000 || seen[res])
              continue;
            seen[res] = true;
            q.push(res);
          }
        }
      }
    }

    return -1;
  }
};

JAVA

class Solution {
  public int minimumOperations(int[] nums, int start, int goal) {
    int ans = 0;
    Queue<Integer> q = new ArrayDeque<>(Arrays.asList(start));
    boolean[] seen = new boolean[1001];
    seen[start] = true;

    while (!q.isEmpty()) {
      ++ans;
      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 ans;
            if (res < 0 || res > 1000 || seen[res])
              continue;
            seen[res] = true;
            q.offer(res);
          }
        }
      }
    }

    return -1;
  }
}

Python

class Solution:
  def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
    ans = 0
    q = deque([start])
    seen = {start}

    while q:
      ans += 1
      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 ans
            if res < 0 or res > 1000 or res in seen:
              continue
            seen.add(res)
            q.append(res)

    return -1