Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/754.html
754. Reach a Number (Easy)
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]
.Companies:
InMobi
Related Topics:
Math
Solution 1.
Try to find pattern:
Firstly, for numbers n(n+1)/2
, they require n
steps, where n >= 1
. For example, 1 = 1
, 3 = 1 + 2
, 6 = 1 + 2 + 3
…
How to get the numbers inbetween?
Think of 2
: the smallest n(n+1)/2
greater than 2
is 3
. If we invert 3
’s component 1
or 2
, we actually subtract 1*2
or 2*2
from 3
. Notice the subtraction is using even number. But 3 - 2 = 1
is an odd number. So we can’t get 2
from 3
.
Consider the next n(n+1)/2
, which is 6
. 6 - 2 = 4
. So we can invert 4 / 2 = 2
in equation 6 = 1 + 2 + 3
to get 2 = 1 - 2 + 3
.
Let’s examine our algorithm with two more test cases.
For 4
, the next n(n+1)/2
is 6
. Since 6 - 4 = 2
, so we can invert 1
in 6 = 1 + 2 + 3
to get 4 = -1 + 2 + 3
.
For 5
:
- check
6
,6 - 5 = 1
, doesn’t work. - check
10 = 1+..+4
,10 - 5 = 5
, doesn’t work. - check
15 = 1+..+5
,15 - 5 = 10
. Works!5 = 1 + 2 + 3 + 4 - 5
.
In sum, keep computing sum = n(n+1)/2
. If sum
is greater than or equal to target
and (sum - target) % 2 == 0
, the corresponding n
is the answer.
// OJ: https://leetcode.com/problems/reach-a-number/
// Time: O(sqrt(T))
// Space: O(1)
class Solution {
public:
int reachNumber(int target) {
int i = 0, sum = 0;
target = abs(target);
while (sum < target || (sum - target) % 2 != 0) {
sum += ++i;
}
return i;
}
};
-
class Solution { public int reachNumber(int target) { target = Math.abs(target); if (target == 0) return 0; int position = 0; int step = 0; while (position < target || position % 2 != target % 2) { step++; position += step; } return step; } } ############ class Solution { public int reachNumber(int target) { target = Math.abs(target); int s = 0, k = 0; while (true) { if (s >= target && (s - target) % 2 == 0) { return k; } ++k; s += k; } } }
-
// OJ: https://leetcode.com/problems/reach-a-number/ // Time: O(sqrt(T)) // Space: O(1) class Solution { public: int reachNumber(int target) { int i = 0, sum = 0; target = abs(target); while (sum < target || (sum - target) % 2 != 0) { sum += ++i; } return i; } };
-
class Solution: def reachNumber(self, target: int) -> int: target = abs(target) s = k = 0 while 1: if s >= target and (s - target) % 2 == 0: return k k += 1 s += k ############ class Solution(object): def reachNumber(self, target): """ :type target: int :rtype: int """ target = abs(target) k = 0 sum = 0 while sum < target: k += 1 sum += k d = sum - target if d % 2 == 0: return k return k + 1 + (k % 2)
-
func reachNumber(target int) int { if target < 0 { target = -target } var s, k int for { if s >= target && (s-target)%2 == 0 { return k } k++ s += k } }
-
/** * @param {number} target * @return {number} */ var reachNumber = function (target) { target = Math.abs(target); let [s, k] = [0, 0]; while (1) { if (s >= target && (s - target) % 2 == 0) { return k; } ++k; s += k; } };