Minimum Operations to Convert Number

Medium
1699.

Minimum Operations to Convert Number

Minimum Operations to Convert Number is a medium coding problem on arrays and breadth-first search, asked in Amazon and Google interviews.

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^9
  • 0 <= start <= 1000
  • start != goal
  • all nums[i] are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} start
 * @param {number} goal
 * @return {number}
 */
var minimumOperations = function(nums, start, goal) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^9
  • 0 <= start <= 1000
  • start != goal
  • all nums[i] are distinct

Hints for Minimum Operations to Convert Number

  1. Hint 1

    Only values inside [0, 1000] can be continued from, so there are at most 1001 interesting states.

  2. Hint 2

    Every operation costs one step — the minimum number of steps is a shortest path in an unweighted graph. Use BFS from start.

  3. Hint 3

    Check each produced value against goal before 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

  1. Keep dist[0..1000] = -1 and set dist[start] = 0; push start into a queue.
  2. Pop x. For every a in nums form x + a, x - a and x XOR a.
  3. If a produced value equals goal, return dist[x] + 1.
  4. Otherwise, if it lies in [0, 1000] and has not been seen, record dist[x] + 1 and push it.
  5. 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 about 10^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 -1

Java

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)