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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Convert Number

Number: 2183

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array of distinct numbers, a starting integer, and a goal integer, find the minimum number of operations needed to convert the start into the goal. In each operation (as long as the current value is in the range [0, 1000]), you can add, subtract, or take bitwise-XOR with any number from the array. Operations that yield a value outside the range are allowed, but no further operations can be performed after leaving the [0, 1000] range. Return -1 if it is not possible.

Key Insights

  • Interpret the problem as a graph search, where each number is a node.
  • Each allowed operation (addition, subtraction, XOR) creates an edge from one number to another.
  • Use Breadth-First Search (BFS) to ensure the first time you hit the goal is with the minimum number of operations.
  • Keep track of visited states within [0, 1000] to avoid cycles and redundant processing.
  • Even if an operation takes x out of [0, 1000], check if it equals the goal before discarding the possibility of a valid solution.

Space and Time Complexity

Time Complexity: O(1001 * N) where N is the number of values in nums, since each state in the range [0, 1000] can be processed up to once. Space Complexity: O(1001) for maintaining the visited states, plus the space for the BFS queue.

Solution

The problem is best approached with a Breadth-First Search (BFS) algorithm where:

  • Each state is represented by the current number and the number of operations taken to reach it.
  • Starting from the initial number, we explore all possible next numbers by applying the allowed operations with every element from the given array.
  • If a generated number equals the goal, we return the number of operations needed.
  • If the generated number is within the valid range (0 to 1000) and has not been seen before, it is added to the BFS queue for further exploration.
  • BFS guarantees that when we first reach the goal, it is achieved with the minimum number of operations.
  • Note the special case where operations produce a number outside [0, 1000]: while further operations cannot be performed on such numbers, we still check if the number equals the goal.

Code Solutions

# Import deque from collections for efficient FIFO queue operations
from collections import deque

def minimumOperations(nums, start, goal):
    # Initialize a BFS queue with (current_value, steps_taken)
    queue = deque([(start, 0)])
    # Set to track visited values in the range [0, 1000] to avoid cycles
    visited = set([start])
    
    while queue:
        current, steps = queue.popleft()
        # Try each operation for each number in nums
        for num in nums:
            # List of possible next values using addition, subtraction, and XOR
            for next_val in (current + num, current - num, current ^ num):
                # If we reached the goal, return steps + 1
                if next_val == goal:
                    return steps + 1
                # Only continue BFS if next_val is within [0, 1000] and not visited
                if 0 <= next_val <= 1000 and next_val not in visited:
                    visited.add(next_val)
                    queue.append((next_val, steps + 1))
    # If goal is unreachable, return -1    
    return -1

# Example usage:
# print(minimumOperations([2,4,12], 2, 12))  # Expected output: 2
← Back to All Questions