Reach a Number LeetCode Solution

Table of Contents

Problem statement:

Reach a Number LeetCode Solution says – You are standing at a position 0 on an infinite number line. There is a destination at the position target.

You can make a number of moves numMoves so that:

On each move, you can either go left or right.
During the i^th 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.

Example 1:

Input:

 target = 2

Output:

Explanation:

On the 1st move, we step from 0 to 1 (1 step). 
On the 2nd move, we step from 1 to -1 (2 steps). 
On the 3rd move, we step from -1 to 2 (3 steps).

Example 2:

Input:

 target = 3

Output:

Explanation:

On the 1st move, we step from 0 to 1 (1 step).
 On the 2nd move, we step from 1 to 3 (2 steps).

Constraints:

-10⁹ <= target <= 10⁹
target != 0

Approach for Reach a Number Leetcode Solution:

1. If the target is negative we just convert it into absolute value. As we are dealing with the symmetric axis.

2. First of all we keep adding sum=1+2+..+n>=target.

3. So, the assumption is when we flip a number then we have to subtract that number from the summation twice.

4. From here we can observe that for flipping we have to subtract twice some number from the summation. So, obviously, we are subtracting an even number.

5. We will get our target step when our summation and target value difference is even number.

Code:

Reach a Number C++ code:

class Solution {
public:
    #define ll long long
   
    int reachNumber(int target) {
        ll cnt=0;
        target=abs(target);
       while(1)
       {
           cnt++;
           ll ans=cnt*(cnt+1)/2;
          
           if(ans>=target)
           {
               ll left=(ans-target);
               if(left%2==0)
                   return cnt;
           }
       }
        return 0;
    }
};

Reach a Number Java code:

class Solution {
    public int reachNumber(int target) {
        target=Math.abs(target);
        int cnt=0;
        while(true)
        {
            cnt++;
            long ans=cnt*(cnt+1)/2;
          
           if(ans>=(long)target)
           {
               long left=(ans-target);
               if(left%2==0)
               {
                   break;
               }
                  
           }
        }
         return cnt;
    }
}

Complexity Analysis of Reach a Number Leetcode Solution:

Time Complexity:

Time Complexity is O(sqrt(n)). Our while loop needs this many steps, as 1+2+…+n=target, n*(n+1)/2=target.

Space Complexity:

Space complexity is O(1). We are not taking any extra space.