Reach a Number

Similar Problems:

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].

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution: math

// https://code.dennyzhang.com/reach-a-number // Basic Ideas: greedy // // Notice: BFS algorithm would be too slow // // Greedy: If keep moving to the right, it will grow the fast // When the difference is even, we only need to switch one previous value // When the difference is odd, add one or two elements to make it event. // Then switch one previous value // // Complexity: Time O(sqrt(n)), Space O(1) func reachNumber(target int) int { if target < 0 { target = -target } i := 0 sum := 0 for sum < target { i++ sum += i } for (sum-target) %2 != 0 { i++ sum += i } return i }