|
1 | 1 | package com.fishercoder.solutions;
|
2 | 2 |
|
3 |
| -/** |
4 |
| - * 754. Reach a Number |
5 |
| - * |
6 |
| - * You are standing at position 0 on an infinite number line. There is a goal at position target. |
7 |
| - * On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps. |
8 |
| - * Return the minimum number of steps required to reach the destination. |
9 |
| -
|
10 |
| - Example 1: |
11 |
| - Input: target = 3 |
12 |
| - Output: 2 |
13 |
| - Explanation: |
14 |
| - On the first move we step from 0 to 1. |
15 |
| - On the second step we step from 1 to 3. |
16 |
| -
|
17 |
| - Example 2: |
18 |
| - Input: target = 2 |
19 |
| - Output: 3 |
20 |
| - Explanation: |
21 |
| - On the first move we step from 0 to 1. |
22 |
| - On the second move we step from 1 to -1. |
23 |
| - On the third move we step from -1 to 2. |
24 |
| -
|
25 |
| - Note: |
26 |
| - target will be a non-zero integer in the range [-10^9, 10^9]. |
27 |
| - */ |
28 |
| - |
29 | 3 | public class _754 {
|
30 |
| - public static class Solution1 { |
31 |
| - /**Two case: |
32 |
| - * 1. go to the right, and reach the goal exactly. |
33 |
| - * 2. go over the goal by several steps: |
34 |
| - * by even number, then you can choose one of the steps that went right to go back to the left (the step is half of what you went over) |
35 |
| - * by odd number, then you keep going until you are over by an even number.*/ |
36 |
| - public int reachNumber(int target) { |
37 |
| - int absTarget = Math.abs(target); |
38 |
| - int steps = 1; |
39 |
| - int sum = 0; |
40 |
| - while (sum < absTarget || (sum - absTarget) % 2 == 1) { |
41 |
| - sum += steps; |
42 |
| - steps++; |
43 |
| - } |
44 |
| - return steps - 1; |
| 4 | + public static class Solution1 { |
| 5 | + /** |
| 6 | + * Two case: |
| 7 | + * 1. go to the right, and reach the goal exactly. |
| 8 | + * 2. go over the goal by several steps: |
| 9 | + * by even number, then you can choose one of the steps that went right to go back to the left (the step is half of what you went over) |
| 10 | + * by odd number, then you keep going until you are over by an even number. |
| 11 | + */ |
| 12 | + public int reachNumber(int target) { |
| 13 | + int absTarget = Math.abs(target); |
| 14 | + int steps = 1; |
| 15 | + int sum = 0; |
| 16 | + while (sum < absTarget || (sum - absTarget) % 2 == 1) { |
| 17 | + sum += steps; |
| 18 | + steps++; |
| 19 | + } |
| 20 | + return steps - 1; |
| 21 | + } |
45 | 22 | }
|
46 |
| - } |
47 | 23 | }
|
0 commit comments