Search

Reach a Number

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.


Example 2:

Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step  from 1 to -1.
On the third move we step from -1 to 2.


Note:

  • target will be a non-zero integer in the range [-10^9, 10^9].

public int reachNumber(int target) {
        int moves=0;
        int sum=0;
        target=Math.abs(target);
        while(sum<target || (sum-target)%2!=0) {
            moves++;
            sum+=moves;
        }
        return moves;
    }

In question it is mentioned that we want to reach at target and to reach there we need to take minimum moves.

we always start from 0 and at each move, we must take i steps.

For example : For target 3, we should take 1 step to reach 1 and now since we can max take -2 or +2 step we will reach 3 here by taking +2 step. and hence output is 2. For target 4, steps could be 0->1 . Then 1->3 and now if we take one more step in positive direction we reach 6. since we have exceeded target we know we must exclude some steps or we can say take some Negative steps. one possible answer can be 0 to -1, -1 to 1, 1 to 4.

To reach above answer we can observe that once we passes target, if the difference of sum-target is even, the output moves remain same. as in above example its still 3. so to break it down in steps,


  1. iterate till sum<target and inside it increase moves and add it to sum.

  2. once loop finishes either sum will be equal to target itself or greater

  3. now run again till will (sum-target)%2 is odd. and increment moves and update sum.

  4. after loop finishes we have reached output moves.

28 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.