Minimum Operations to Convert Number — Problem & Solution
Minimum Operations to Convert Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimum Operations to Convert Number is a medium coding problem on arrays and breadth-first search, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Breadth-First Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array nums of distinct integers, a starting value start and a target value goal.
A variable x begins at start. While 0 <= x <= 1000, you may apply any of these operations, using any element nums[i] any number of times:
x = x + nums[i]x = x - nums[i]x = x XOR nums[i](bitwise exclusive or)
An operation is allowed to take x outside the range [0, 1000], but once x is outside that range no further operation can be applied.
Return the minimum number of operations needed to turn start into goal, or -1 if it cannot be done.
Example 1
Input: nums = [2,4,12], start = 2, goal = 12
Output: 2
Explanation: 2 + 12 = 14, then 14 - 2 = 12.
Example 2
Input: nums = [3,5,7], start = 0, goal = -4
Output: 2
Explanation: 0 + 3 = 3, then 3 - 7 = -4. Leaving the range is fine on the last step.
Example 3
Input: nums = [2,8,16], start = 0, goal = 1
Output: -1
Explanation: Every value reachable from 0 is even, so 1 never appears.
Constraints
1 <= nums.length <= 1000-10^9 <= nums[i], goal <= 10^90 <= start <= 1000start != goalall nums[i] are distinct
Hints for Minimum Operations to Convert Number
Hint 1
Only values inside
[0, 1000]can be continued from, so there are at most 1001 interesting states.Hint 2
Every operation costs one step — the minimum number of steps is a shortest path in an unweighted graph. Use BFS from
start.Hint 3
Check each produced value against
goalbefore checking the range: the final step may leave[0, 1000].
How to solve Minimum Operations to Convert Number
Treat every value in [0, 1000] as a node and every operation as an edge of length 1. A breadth-first search from start meets each value at its smallest number of operations, and the goal may be produced by the last step even when it lies outside the range.
Approach
- Keep
dist[0..1000] = -1and setdist[start] = 0; pushstartinto a queue. - Pop
x. For everyainnumsformx + a,x - aandx XOR a. - If a produced value equals
goal, returndist[x] + 1. - Otherwise, if it lies in
[0, 1000]and has not been seen, recorddist[x] + 1and push it. - If the queue empties, return
-1.
Why it works
BFS removes states in non-decreasing order of distance, so the first time goal is produced it is produced with the fewest operations. Values outside the range can never be extended, so they only matter as possible goals, which is exactly the check made when a value is produced.
Complexity
- Time —
O(1001 · n) - Space —
O(1001)
Pitfalls
- Do not discard an out-of-range value before comparing it to
goal— Example 2 ends at -4. - XOR with a negative number works on two's complement; every language here gives the same result for 32-bit values.
x + nums[i]can reach about10^9 + 1000, which still fits a 32-bit integer.
Reference solution
Python
from typing import List
from collections import deque
def minimumOperations(nums: List[int], start: int, goal: int) -> int:
dist = [-1] * 1001
dist[start] = 0
q = deque([start])
while q:
x = q.popleft()
d = dist[x] + 1
for a in nums:
for y in (x + a, x - a, x ^ a):
if y == goal:
return d
if 0 <= y <= 1000 and dist[y] < 0:
dist[y] = d
q.append(y)
return -1Java
public static int minimumOperations(int[] nums, int start, int goal) {
int[] dist = new int[1001];
Arrays.fill(dist, -1);
int[] q = new int[1001];
int head = 0, tail = 0;
dist[start] = 0;
q[tail++] = start;
while (head < tail) {
int x = q[head++], d = dist[x] + 1;
for (int a : nums) {
int[] cand = {x + a, x - a, x ^ a};
for (int y : cand) {
if (y == goal) return d;
if (y >= 0 && y <= 1000 && dist[y] < 0) { dist[y] = d; q[tail++] = y; }
}
}
}
return -1;
}C++
int minimumOperations(vector<int>& nums, int start, int goal) {
vector<int> dist(1001, -1);
vector<int> q;
dist[start] = 0;
q.push_back(start);
for (size_t h = 0; h < q.size(); h++) {
int x = q[h], d = dist[x] + 1;
for (int a : nums) {
int cand[3] = {x + a, x - a, x ^ a};
for (int y : cand) {
if (y == goal) return d;
if (y >= 0 && y <= 1000 && dist[y] < 0) { dist[y] = d; q.push_back(y); }
}
}
}
return -1;
}JavaScript
var minimumOperations = function(nums, start, goal) {
var dist = new Array(1001);
for (var i = 0; i <= 1000; i++) dist[i] = -1;
dist[start] = 0;
var q = [start];
for (var h = 0; h < q.length; h++) {
var x = q[h], d = dist[x] + 1;
for (var j = 0; j < nums.length; j++) {
var a = nums[j];
var cand = [x + a, x - a, x ^ a];
for (var t = 0; t < 3; t++) {
var y = cand[t];
if (y === goal) return d;
if (y >= 0 && y <= 1000 && dist[y] < 0) { dist[y] = d; q.push(y); }
}
}
}
return -1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Breadth-First Search (BFS)