# 754. 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]`.

0 + 1 = 1

1 + 2 = 3

3 + 3 = 6

0 - 1 = -1

-1 + 2 = 1

1 + 3 = 4

target = n * (n + 1) / 2

n^2 + n - 2*target = 0

n = (-1 + sqrt(1 + 8*target)) / 2

``````class Solution {
public:
int reachNumber(int target) {
target = abs(target);
long n = ceil((-1.0 + sqrt(1 + 8.0 * target)) / 2);
long sum = n * (n + 1) / 2;
if (sum == target) return n;
long res = sum - target;
if ((res & 1) == 0) return n;
return n + ((n & 1) ? 2 : 1);
}
};
``````

``````class Solution {
public:
int reachNumber(int target) {
target = abs(target);
int res = 0, sum = 0;
while (sum < target || (sum - target) % 2 == 1) {
++res;
sum += res;
}
return res;
}
};
``````

``````class Solution {
public:
int reachNumber(int target) {
int n = ceil((sqrt(1 + 8.0 * abs(target)) - 1) / 2), d = n * (n + 1) / 2 - target;
return n + (d % 2) * (n % 2 + 1);
}
};
``````

Github 同步地址：

https://github.com/grandyang/leetcode/issues/754

https://leetcode.com/problems/reach-a-number/

https://leetcode.com/problems/reach-a-number/discuss/112969/C++-O(1)-Solution-without-loop

https://leetcode.com/problems/reach-a-number/discuss/112992/Learn-from-other-with-my-explanations

https://leetcode.com/problems/reach-a-number/discuss/112982/2-liner-a-math-problem-with-explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation