-
Notifications
You must be signed in to change notification settings - Fork 0
/
Reach a Number
38 lines (38 loc) · 1.35 KB
/
Reach a Number
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/* Programmer : Dhruv Patel
* Problem Name : Reach a Number
* Used In : Leetcode
* Used As : weekly-contest-65
* Thoughts =>
* 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.
* Time Complexity=>
* O(N)
*/
public static int reachNumber(int target) {
target = Math.abs(target);
int step = 0;
int sum = 0;
while (sum < target) {
step++;
sum += step;
}
while ((sum - target) % 2 != 0) {
step++;
sum += step;
}
return step;
}