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

Reach a Number

Difficulty: Medium

Problem Description

You are standing at position 0 on an infinite number line. There is a destination at position target. You can make some number of moves numMoves so that:

  • On each move, you can either go left or right.
  • During the ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction.

Given the integer target, return the minimum number of moves required (i.e., the minimum numMoves) to reach the destination.

Key Insights

  • The sum of the first n natural numbers is given by the formula n * (n + 1) / 2.
  • To reach the target, the total distance covered must be equal to or greater than the absolute value of the target.
  • The excess distance (total distance - target) must be even to allow for the possibility of balancing left and right moves.
  • We need to find the smallest n such that the sum of moves is sufficient to reach or exceed the target and allows for balancing.

Space and Time Complexity

Time Complexity: O(√n) - We loop until we find the minimum n. Space Complexity: O(1) - We only use a few variables for calculations.

Solution

To solve this problem, we can use a simple iterative approach to find the smallest number of moves required. We keep track of the total distance we can cover with the moves and check if we can reach or exceed the target while ensuring that the excess distance can be balanced. This involves checking if the excess distance is even.

Code Solutions

def reachNumber(target: int) -> int:
    target = abs(target)  # We can work with the absolute value
    moves = 0
    total_distance = 0
    
    while True:
        moves += 1
        total_distance += moves
        # Check if we have reached or exceeded the target
        if total_distance >= target and (total_distance - target) % 2 == 0:
            return moves
← Back to All Questions