You are standing at position 0 on an infinite number line. There is a destination at position target.
You can make some number of moves numMoves so that:
ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction.Given the integer target, return the minimum number of moves required (i.e., the minimum numMoves) to reach the destination.
Example 1:
Input: target = 2 Output: 3 Explanation: On the 1st move, we step from 0 to 1 (1 step). On the 2nd move, we step from 1 to -1 (2 steps). On the 3rd move, we step from -1 to 2 (3 steps).
Example 2:
Input: target = 3 Output: 2 Explanation: On the 1st move, we step from 0 to 1 (1 step). On the 2nd move, we step from 1 to 3 (2 steps).
Constraints:
-109 <= target <= 109target != 0In #754 Reach a Number, the goal is to determine the minimum number of moves needed to reach a target on a number line. On the k-th move, you can move k steps either left or right. A key observation is that the total distance after k moves equals the sum of the first k natural numbers. The strategy is to keep increasing the move count until this cumulative distance becomes greater than or equal to the absolute value of the target.
However, reaching the target exactly depends on the parity of the difference between the accumulated sum and the target. If the difference is even, you can flip the direction of certain moves to adjust the total distance. Otherwise, you continue increasing the number of moves until the parity condition is satisfied.
This approach leverages mathematical reasoning rather than brute force exploration. The cumulative sum grows quickly, making the algorithm efficient for large targets.
Time Complexity: O(√target) since the cumulative sum grows quadratically. Space Complexity: O(1).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Mathematical / Greedy using cumulative sum and parity check | O(√target) | O(1) |
| Binary search on number of moves (conceptual alternative) | O(log target) | O(1) |
NeetCode
This approach involves breaking down the problem into smaller subproblems, solving each subproblem recursively, and then combining the results. This is a classic Divide and Conquer approach which can be applied to a variety of problems, such as sorting algorithms (e.g., Merge Sort).
Time Complexity: O(n log n)
Space Complexity: O(n)
1function merge(arr, left, mid, right) {
2 const n1 = mid - left + 1;
3 const n2 = right - mid;
4 const L = new Array(n1);
5 const R = new Array(n2);
6
7 for (let i = 0; i < n1; i++)
8 L[i] = arr[left + i];
9 for (let j = 0; j < n2; j++)
10 R[j] = arr[mid + 1 + j];
11
12 let i = 0, j = 0, k = left;
13 while (i < n1 && j < n2) {
14 if (L[i] <= R[j]) {
15 arr[k] = L[i];
16 i++;
17 } else {
18 arr[k] = R[j];
19 j++;
20 }
21 k++;
22 }
23
24 while (i < n1) {
25 arr[k] = L[i];
26 i++;
27 k++;
28 }
29
30 while (j < n2) {
31 arr[k] = R[j];
32 j++;
33 k++;
34 }
35}
36
37function mergeSort(arr, left, right) {
38 if (left < right) {
39 const mid = left + Math.floor((right - left) / 2);
40
41 mergeSort(arr, left, mid);
42 mergeSort(arr, mid + 1, right);
43
44 merge(arr, left, mid, right);
45 }
46}
47
48let arr = [12, 11, 13, 5, 6, 7];
49mergeSort(arr, 0, arr.length - 1);
50console.log("Sorted array:", arr);This JavaScript code provides a Merge Sort implementation. It makes use of the merge function to merge two sorted parts of an array and applies recursion in the mergeSort function to divide the array into smaller parts.
Dynamic Programming (DP) is an approach that solves complex problems by breaking them down into simpler subproblems and storing the results to avoid recomputing. It's particularly useful for optimization problems where decisions depend on previous decisions.
Time Complexity: O(n)
Space Complexity: O(n)
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Parity determines whether the difference between the accumulated sum and the target can be corrected by reversing the direction of certain moves. Flipping a move changes the total distance by an even value, so the difference must be even.
Yes, conceptually you can use binary search to find the smallest number of moves where the cumulative sum reaches or exceeds the target. However, the common solution relies on direct mathematical iteration and parity checks.
Yes, this problem is a common medium-level interview question because it tests mathematical reasoning and pattern recognition. Interviewers often expect candidates to derive the parity-based insight rather than simulate moves.
The optimal approach uses a mathematical observation about cumulative sums of natural numbers. You increase the move count until the sum of steps is at least the absolute target, then check if the difference has even parity to adjust directions.
This C code demonstrates a dynamic programming solution for computing Fibonacci numbers. It uses memoization to store previously calculated results in the dp array, avoiding redundant calculations.