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)
1#include <stdio.h>
2
3void merge(int arr[], int left, int mid, int right) {
4 int i, j, k;
5 int n1 = mid - left + 1;
6 int n2 = right - mid;
7 int L[n1], R[n2];
8
9 for (i = 0; i < n1; i++)
10 L[i] = arr[left + i];
11 for (j = 0; j < n2; j++)
12 R[j] = arr[mid + 1 + j];
13
14 i = 0;
15 j = 0;
16 k = left;
17 while (i < n1 && j < n2) {
18 if (L[i] <= R[j]) {
19 arr[k] = L[i];
20 i++;
21 } else {
22 arr[k] = R[j];
23 j++;
24 }
25 k++;
26 }
27
28 while (i < n1) {
29 arr[k] = L[i];
30 i++;
31 k++;
32 }
33
34 while (j < n2) {
35 arr[k] = R[j];
36 j++;
37 k++;
38 }
39}
40
41void mergeSort(int arr[], int left, int right) {
42 if (left < right) {
43 int mid = left + (right - left) / 2;
44
45 mergeSort(arr, left, mid);
46 mergeSort(arr, mid + 1, right);
47
48 merge(arr, left, mid, right);
49 }
50}
51
52int main() {
53 int arr[] = {12, 11, 13, 5, 6, 7};
54 int arr_size = sizeof(arr) / sizeof(arr[0]);
55
56 mergeSort(arr, 0, arr_size - 1);
57
58 printf("Sorted array: \n");
59 for (int i = 0; i < arr_size; i++)
60 printf("%d ", arr[i]);
61 return 0;
62}This C code implements the Merge Sort algorithm using the Divide and Conquer strategy. The array is divided into two halves, each is sorted recursively, and then the two halves are merged together. The merge function combines two sorted subarrays into a single sorted array.
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#include <iostream>
2#include <vector>
using namespace std;
int fib(int n, vector<int>& dp) {
if (n <= 1)
return n;
if (dp[n] != -1)
return dp[n];
return dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
}
int main() {
int n = 10;
vector<int> dp(n + 1, -1);
cout << "Fibonacci number is " << fib(n, dp) << endl;
return 0;
}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 implements a Fibonacci sequence calculator using Dynamic Programming. Memoization is employed to store results of previous computations in a vector, eliminating redundant calculations and reducing execution time.