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

Reach a Number

Number: 755

Difficulty: Medium

Paid? No

Companies: Commvault, Amazon, Sprinklr, InMobi

Problem Description

We start at position 0 on an infinite number line and want to reach a target position using a series of moves. On the iᵗʰ move, we can take exactly i steps either to the right or left. Our goal is to determine the minimum number of moves required to reach the given target.

Key Insights

  • Due to symmetry, work with the absolute value of the target.
  • The sum of the first n natural numbers is n(n+1)/2. We need this sum to be at least the absolute target.
  • Flipping a move changes the total by an even number. Therefore, the difference between the sum and the target must be even.
  • Iterate n until both conditions are met: total distance is large enough and the difference (total - target) is even.

Space and Time Complexity

Time Complexity: O(n), where n is the minimum number of moves needed (typically much smaller than target). Space Complexity: O(1).

Solution

The approach first converts the target to its absolute value. We then search for the smallest integer n such that the sum of the first n natural numbers (S = n(n+1)/2) is at least the target and (S - target) is even. This even difference indicates that we can flip the signs of certain moves to exactly hit the target. The solution uses a simple iterative method to find such n.

Code Solutions

# Python solution with line-by-line comments

def reachNumber(target):
    # Use absolute value since the problem is symmetric
    target = abs(target)
    moves = 0
    total = 0

    # Iterate until the total sum is at least target and the difference is even
    while total < target or (total - target) % 2 != 0:
        moves += 1            # Increment the move count
        total += moves        # Add the current move steps to total
    # When found, moves is the required minimum number of moves
    return moves

# Example usage:
if __name__ == "__main__":
    print(reachNumber(2))  # Output: 3
    print(reachNumber(3))  # Output: 2
← Back to All Questions