0754. 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].
Analysis¶
It's a math problem, and we can use Pythagorean theorem to calculate the minimal steps to reach or be greater than target number, and then by flipping one or some of the step(s), we can finally reach the perfect number. There are two cases when our first minimal steps exceeds the target, and we represent the difference as diff:
diffis an odd number: in this case, we just need to keep proceeding (step ++), because by flipping any number from 1 to step, it will result in a 2 * step number, which guarantees to be a even number.-
diffis even: great, we can just flip a step within 1 to step, since we can guaranteediffis always less than latest step, we can be sure that there is aflip stepexist so that 2 *flip step= diff. -
Time: O(1) by using math
- Space: O(1)
Why it can guarantee to be the optimal solution? leetcode url
Code¶
Without using math:
class Solution {
public:
int reachNumber(int target) {
target = abs(target);
int step = 0, sum = 0;
for (; sum < target; sum += step)
step ++;
while ((sum - target) % 2 != 0) {
sum += ++step;
}
return step;
}
};
Using Pythagorean theorem:
class Solution {
public:
int reachNumber(int64_t target) {
target = std::abs(target);
int64_t steps = 0.5*(sqrt(8*target)-1)+1, sum{(steps+1)*steps/2}, diff{sum - target};
if(diff % 2 == 0) return steps;
else if(steps % 2 == 0) return steps + 1;
return steps + 2;
}
};