We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Convert Number

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be viewed as finding the shortest path in an unweighted graph where nodes represent possible values of x and edges represent operations (add, subtract, XOR).
  • A Breadth-First Search (BFS) approach is suitable since we want the minimum number of operations to reach the goal from the start.
  • The BFS will explore all possible operations from the current value of x and track visited states to avoid cycles and redundant calculations.
  • The operations can lead to values outside the range of 0 <= x <= 1000, which allows for exploring paths that may ultimately reach the goal.

Space and Time Complexity

Time Complexity: O(N * C), where N is the number of elements in nums and C is the number of reachable states (in this case, we can consider C as the range of possible values for x). Space Complexity: O(C), where C is the number of reachable states, due to the storage of visited states and the BFS queue.

Solution

The solution involves using a Breadth-First Search (BFS) algorithm to explore all possible values of x starting from start. We maintain a queue to explore each state, and a set to track visited states to avoid cycles. For each state, we apply all operations using elements from nums, add the resulting states to the queue, and continue until we find goal or exhaust all possibilities.

Code Solutions

from collections import deque

def min_operations(nums, start, goal):
    queue = deque([(start, 0)])  # (current value of x, number of operations)
    visited = set([start])  # track visited states
    
    while queue:
        current, steps = queue.popleft()
        
        if current == goal:
            return steps
        
        for num in nums:
            for next_value in (current + num, current - num, current ^ num):
                if next_value == goal:
                    return steps + 1
                if 0 <= next_value <= 1000 and next_value not in visited:
                    visited.add(next_value)
                    queue.append((next_value, steps + 1))
    
    return -1
← Back to All Questions