Minimum Operations to Convert Number - Practice Coding Problems

Minimum Operations to Convert Number - Problem

You are given a 0-indexed integer array nums containing distinct numbers, an integer start, and an integer goal. There is an integer x that is initially set to start, and you want to perform operations on x such that it is converted to goal.

You can perform the following operation repeatedly on the number x:

If 0 <= x <= 1000, then for any index i in the array (0 <= i < nums.length), you can set x to any of the following:

x + nums[i]
x - nums[i]
x ^ nums[i] (bitwise-XOR)

Note that you can use each nums[i] any number of times in any order. Operations that set x to be out of the range 0 <= x <= 1000 are valid, but no more operations can be done afterward.

Return the minimum number of operations needed to convert x = start into goal, and -1 if it is not possible.

Input & Output

Example 1 — Basic Transformation

$ Input: nums = [2,3], start = 3, goal = 10

› Output: 2

💡 Note: We can transform 3 → 5 (3+2) → 10 (5+3+2). Total 2 operations needed.

Example 2 — XOR Operation

$ Input: nums = [3,5,1,4,2], start = 0, goal = 11

› Output: 3

💡 Note: Transform 0 → 3 (0^3) → 7 (3^4) → 11 (7^4). Using XOR operations efficiently.

Example 3 — Impossible Case

$ Input: nums = [2,4,6], start = 1, goal = 8

› Output: -1

💡 Note: Cannot reach 8 from 1 using only even numbers within the valid range 0-1000.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000
0 ≤ start, goal ≤ 1000
All the integers in nums are distinct

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums, start value, and goal value

Transform

Use +, -, ^ operations with array elements

Result

Minimum operations to reach goal or -1 if impossible

Key Takeaway

🎯 Key Insight: Use BFS to explore all possible transformations level by level, guaranteeing the shortest path to the goal

Asked in

G Google 28 f Facebook 15 a Amazon 12

The key insight is that this is a shortest path problem in an unweighted graph where nodes are numbers (0-1000) and edges are the three operations. BFS guarantees finding the minimum number of operations by exploring all states level by level. Time: O(1000 × n), Space: O(1000)

Common Approaches

Approach	Time	Space	Notes
✓ DFS with All Possibilities	O(3^n)	O(n)	Try all possible operations recursively until goal is reached
BFS with Queue	O(1000 * n)	O(1000)	Use breadth-first search to find shortest transformation path

DFS with All Possibilities — Algorithm Steps

Start with x = start
For each nums[i], try x+nums[i], x-nums[i], x^nums[i]
Recursively explore each possibility
Return minimum operations found

Visualization

Tap to expand

Step-by-Step Walkthrough

Start State

Begin with x = start value

Try Operations

For each nums[i], try +, -, ^ operations

Recurse

Explore each branch until goal found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int dfs(int* nums, int numsSize, int x, int goal, int ops) {
    if (x == goal) return ops;
    if (x < 0 || x > 1000 || ops > 10) return INT_MAX;
    
    int minOps = INT_MAX;
    for (int i = 0; i < numsSize; i++) {
        int op1 = dfs(nums, numsSize, x + nums[i], goal, ops + 1);
        int op2 = dfs(nums, numsSize, x - nums[i], goal, ops + 1);
        int op3 = dfs(nums, numsSize, x ^ nums[i], goal, ops + 1);
        if (op1 < minOps) minOps = op1;
        if (op2 < minOps) minOps = op2;
        if (op3 < minOps) minOps = op3;
    }
    return minOps;
}

int solution(int* nums, int numsSize, int start, int goal) {
    int result = dfs(nums, numsSize, start, goal, 0);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[100];
    int numsSize = 0;
    char* ptr = strchr(line, '[') + 1;
    char* end = strchr(line, ']');
    *end = '\0';
    
    char* token = strtok(ptr, ",");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",");
    }
    
    int start, goal;
    scanf("%d", &start);
    scanf("%d", &goal);
    
    printf("%d\n", solution(nums, numsSize, start, goal));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(3^n)

Each operation creates 3 branches, explored to depth n

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth proportional to number of operations

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with All Possibilities — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler