754. Reach a Number
Problem Description
This problem places you at position 0
on an infinite number line, with a goal to reach a specific position called target
. The objective is to find the minimum number of moves required to reach target
. With each move, numMoves
, you can step either to the left or right, and with each subsequent move, you increase the number of steps you take by 1
. For example, in your first move, you'll take 1 step, in the second move, 2 steps, and so on, increasing the steps by one with each move.
Understand that because the line is infinite and moves can be in both directions, reaching a position with a minimum number of moves involves a combination of steps that add up to either the target itself or a number where if we changed the direction of any move, we could end up at the target. For instance, if our sum surpasses the target by a number that is even, we can flip the direction of a move that corresponds to half that excess number, since moving in the opposite direction will reduce the sum by twice the number of that move.
Intuition
The solution to this problem relies on the realization that moving left or right can be thought of in terms of sums and differences. The aim is to find the smallest k
, the minimum number of moves, such that when we sum the numbers from 1
to k
, the result is either equal to or greater than the target
. However, that's not enough. Since we need to be able to reach the exact target, the excess (the difference between the sum and the target) has to be an even number. This is because any odd-numbered excess cannot be compensated for by flipping a single move's direction.
Once we reach or exceed the target, if the excess is even, we can imagine that we can flip the direction of one or more moves to adjust the sum exactly to the target. To illustrate why we can only adjust with an even difference, picture a number line, and consider that every move at ith step moves by i
units. If we flip the direction of the i
step after exceeding the target, it would mean we subtract 2*i
units from the total sum (since we're now considering that we moved i
units in the opposite direction) - which means the adjustment is always even.
The solution code implements this thought process by starting with s
and k
at 0
, where s
represents the sum of moves and k
represents the count of moves. The code enters a loop that increments k
with each iteration, effectively simulating each step, and adds k
to s
. After each step, the code checks if s
has reached or exceeded the target and if s - target
is an even number. If both conditions are met, k
is the minimum number of moves required, and the loop ends, returning k
.
Thus, we arrive at the minimum number of moves required to reach the exact target
on the number line.
Learn more about Math and Binary Search patterns.
Solution Approach
The solution uses a simple mathematical approach rather than advanced algorithms or data structures. It employs a while loop to iterate through the possible number of moves, incrementally summing the number of steps and checking the condition to find the minimum moves to the target.
Here is a step-by-step breakdown of the implementation using the code provided:
-
The target is made non-negative by
target = abs(target)
. Because the number line is symmetrical, it doesn't matter if the target is to the left or right of0
. -
Two variables are initialized:
s
andk
.s
is used to hold the cumulative sum of steps taken, whilek
counts the number of moves. -
A while loop begins, which will run indefinitely until the exit condition is met. The exit condition checks two things:
- Whether the cumulative sum
s
is greater than or equal totarget
. This means we have reached or surpassed the target. - Whether the difference between the sum
s
and thetarget
is even ((s - target) % 2 == 0
). This means we can 'flip' one or more steps to adjust the sum to exactly match the target.
- Whether the cumulative sum
-
Inside the loop, with each iteration:
- First,
k
is incremented by1
, representing the next move. - Then
s
is increased byk
, reflecting the addition ofk
steps for that move.
- First,
-
Once the exit condition is satisfied (i.e.,
s >= target
and(s - target) % 2 == 0
),k
represents the minimum number of moves required to reach thetarget
, and is returned from the function.
The pattern utilized in this solution is straightforward incremental search. The code successively tries the next possible number of steps until the target condition is satisfied. It leverages the mathematical property that any number of steps that exceeds the target must have an even difference from the target in order for the sum of steps to be adjustable to that target. The solution is efficient, with a time complexity of O(sqrt(target)) since it takes about ā(2*target) iterations to find the answer in the worst-case scenario.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Consider the example where the target
position is 3
. We aim to find the minimum number of moves to reach this position from 0
.
Let's apply the solution approach step-by-step:
-
First, we take the absolute value of
target
, which remains3
since it is already positive. -
We initialize
s = 0
(the cumulative sum of steps) andk = 0
(the count of moves). -
We run a while loop which will continue until
s >= target
and(s - target) % 2 == 0
. -
In the first iteration:
- Increment
k
to1
(first move). - Add
k
tos
, makings = 0 + 1 = 1
. - Check if
s >= target
:1
is not greater than or equal to3
, so continue.
- Increment
-
Second iteration:
- Increment
k
to2
(second move). - Add
k
tos
, makings = 1 + 2 = 3
. - Check if
s >= target
:3
is equal to3
, and(s - target) % 2 == 0
(since0 % 2 == 0
), conditions are satisfied.
- Increment
Since both the exit conditions are satisfied after the second move, the while loop ends. We found that k = 2
represents the minimum number of moves to reach the target
of 3
.
Thus, the answer is 2
.
This example illustrates the process of incrementing each step and checking the conditions until the minimum set of moves that satisfies both s >= target
and evenness of (s - target)
is found. It shows the efficiency of the approach, as it avoids unnecessary calculations and quickly converges to the correct minimum number of moves.
Solution Implementation
1class Solution:
2 def reachNumber(self, target: int) -> int:
3 # Take absolute value of target since it's symmetric around 0
4 target = abs(target)
5 # Initialize sum and step counter
6 total_sum = step = 0
7
8 # Keep stepping until the conditions are met
9 while True:
10 # Check if total_sum meets or exceeds target and the difference
11 # between total_sum and target is even (allowing to reach target by flipping some steps)
12 if total_sum >= target and (total_sum - target) % 2 == 0:
13 # If conditions met, return the number of steps taken
14 return step
15
16 # Increment step count
17 step += 1
18 # Update total_sum by adding the current step
19 total_sum += step
20
1class Solution {
2
3 // Calculates the minimum number of steps required to reach a specific target number.
4 // The method works by moving 1 step in the first move, 2 steps in the second,
5 // and so on until it either passes the target or lands on it. If the sum is more
6 // than the target and the difference between sum and target is even,
7 // it means we can adjust the steps to reach the target exactly.
8 public int reachNumber(int target) {
9 // Absolute value is taken because the symmetry of the problem
10 // means that the same number of steps will be needed to reach -target.
11 target = Math.abs(target);
12
13 int sum = 0; // Initialize the sum of steps to zero.
14 int step = 0; // Initialize the step count to zero.
15
16 while (true) {
17 // Check if the sum is at least as large as the target and
18 // if the difference between sum and target is even.
19 if (sum >= target && (sum - target) % 2 == 0) {
20 // The minimum number of steps required to reach the target is found.
21 return step;
22 }
23
24 // Increment the step count for the next iteration.
25 step++;
26 // Add the current step count to the total sum.
27 sum += step;
28 }
29 }
30}
31
1class Solution {
2public:
3 int reachNumber(int target) {
4 // Taking absolute value since the problem is symmetric about the origin
5 target = abs(target);
6
7 // Initialize the sum of steps taken and the number of steps
8 int sum = 0;
9 int step = 0;
10
11 // Use an infinite loop to determine the minimum number of steps
12 while (true) {
13 // As soon as we reach or surpass the target
14 // and the difference between the sum and target is even,
15 // we can return the current step count.
16 // The condition for an even difference is because
17 // we can use negative steps to adjust for an even difference.
18 if (sum >= target && (sum - target) % 2 == 0) {
19 return step;
20 }
21
22 // Increment the step before adding it to the sum
23 // since the next position depends on the next step
24 ++step;
25
26 // Add the current step value to the sum
27 sum += step;
28 }
29 }
30};
31
1// Function to determine the minimum number of steps required to reach a target number on a number line
2// where in the first move you can either go left or right by 1, second move, left or right by 2, and so on.
3/**
4 * @param {number} target - The target number to reach on the number line
5 * @return {number} - The minimum number of steps required to reach the target number
6 */
7function reachNumber(target: number): number {
8 // Take the absolute value of the target to work with positive numbers, as the problem is symmetric
9 target = Math.abs(target);
10 // Initialize the sum of steps(s) and step count(k) to zero
11 let sum: number = 0;
12 let stepCount: number = 0;
13
14 // Loop indefinitely, as we will return from within the loop once the condition is met
15 while (true) {
16 // If the sum of steps is at least as much as the target
17 // and the difference between sum and target is even
18 // (which means we can reach the target by flipping the direction of the required moves),
19 // then return the step count as result.
20 if (sum >= target && (sum - target) % 2 === 0) {
21 return stepCount;
22 }
23 // Increment the step count, this also represents the step size to be added to sum
24 stepCount++;
25 // Increment the sum of steps by the current step count
26 sum += stepCount;
27 }
28}
29
30// Note: The return type number after function declaration indicates that this function returns a number
31
Time and Space Complexity
The provided code is a solution to find the minimum number of steps to reach a specific number on a number line starting from zero, where in the nth
step, you can either walk to the left or right n
units.
Time Complexity
The time complexity of the code is determined by how many iterations the while loop performs before reaching a condition where the sum s
is greater than or equal to target
and the difference (s - target)
is an even number.
Since in each iteration k
is incremented by 1 and added to s
, the sum s
forms an arithmetic sequence. The number of iterations is essentially the smallest k
such that s >= target
and (s - target)
is even, where s
is the k
th triangular number, given by the formula s = k * (k + 1) / 2
.
In the worst-case scenario, this sequential increase leads us to a series of additions that is roughly of the order of the square root of the target value (O(sqrt(target))
) due to the nature of the triangular number series.
Therefore, the time complexity is O(sqrt(target))
.
Space Complexity
The space complexity of the code is O(1)
because a constant number of variables are used regardless of the input size. The variables target
, s
, and k
do not depend on the input size in a way that would require more space as target
increases.
To sum up, the time complexity is O(sqrt(target))
and the space complexity is O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we