Python 0754.py
class Solution:
def reachNumber(self, target: int) -> int:
# triangle numbers
def tri(x):
return x * (x + 1) // 2
target = abs(target)
a = floor((target*2)**0.5) - 1
while tri(a) < target:
a += 1
while (tri(a) - target) % 2 == 1:
a += 1
return a
Difficulty
and has an acceptance rate of about 44% (100k+ submissions).
Typical patterns to solve this problem:
- Binary Search
- Math
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided Solution.reachNumber method determines the smallest number of sequential moves required to reach a given integer target on a one-dimensional line. Each move i advances the position by exactly i units, and the direction of each move may be chosen freely. The algorithm leverages properties of triangular numbers to compute the answer efficiently without exhaustive simulation.
Key Steps
Normalizing the Target
target = abs(target)
The problem is symmetric with respect to the origin; reaching -k requires the same number of moves as reaching k. By converting the input to its absolute value, the subsequent calculations can assume a non-negative target, simplifying the logic.
Computing an Initial Estimate
a = floor((target*2)**0.5) - 1
The sum of the first a natural numbers is the triangular number a·(a+1)/2. Solving the inequality a·(a+1)/2 ≥ target for a yields an approximate lower bound. The expression (target*2)**0.5 computes the square root of 2·target, and floor truncates it to the nearest integer not exceeding the true root. Subtracting one provides a conservative starting point that is guaranteed not to overshoot the required sum.
Adjusting to Reach or Exceed the Target
while tri(a) < target:
a += 1
The helper tri returns the exact triangular number for a given a. If the initial estimate falls short, this loop increments a until the cumulative distance tri(a) meets or exceeds the target. Because each increment increases the triangular sum by a+1, the loop converges quickly, typically in at most a few iterations.
Ensuring the Parity Condition
while (tri(a) - target) % 2 == 1:
a += 1
Reaching the exact target may require flipping the direction of some moves. Flipping a move of length i changes the net displacement by 2·i. Consequently, the difference between the current triangular sum and the target must be an even number to be representable as a sum of such flips. This loop increments a until the parity of tri(a) - target becomes even, guaranteeing that a suitable combination of forward and backward moves exists.
Returning the Result
return a
At this point a is the minimal step count satisfying both the magnitude and parity constraints, and the method returns it as the answer.
Edge Cases Handled
When the input target is zero, the absolute conversion yields 0. The initial estimate a becomes -1 after the subtraction, but the first while loop immediately increments a to 0 because tri(0) equals 0, satisfying the condition tri(a) >= target. The parity loop does not execute because the difference is already even, and the method returns 0, correctly indicating that no moves are needed.
For negative inputs, the absolute conversion ensures the same path length as the corresponding positive value, so the algorithm does not need separate handling for sign.
Very small positive targets such as 1 or 2 are also covered. The initial estimate may start below the required step count, but the adjustment loops quickly raise a to the smallest feasible value, respecting both the sum and parity requirements.
Performance Optimizations
The algorithm avoids brute-force enumeration of all possible move sequences. By directly estimating a lower bound using the square-root formula, it reduces the number of iterations needed to reach a valid a. The triangular number helper computes a·(a+1)//2 in constant time, and the loops increment a only when necessary, guaranteeing rapid convergence.
Using integer arithmetic throughout (the // operator for the triangular number and the % operator for parity) eliminates floating-point overhead and ensures exact comparisons. The floor function from the math library provides an efficient integer approximation without resorting to more costly iterative methods.
Overall, the method achieves the result with a minimal number of arithmetic operations and loop iterations, making it well-suited for large input values.
ELI5 - Simplified Explanation
Imagine a little bouncy ball on a long path of numbered tiles. The goal is to reach a specific number, which could be positive like five or negative like minus five. Because movement works the same way in both directions, the first step is to treat every target as a positive number.
Starting at zero, the plan is to take jumps of increasing size. The first jump moves one tile, the second jump moves two, then three, and so on. A special math tool adds up all these jump lengths to see where the ball lands after a certain number of moves. The code keeps track of these totals to find the first moment the ball lands at or beyond the target number.
Sometimes the ball travels a bit too far past the target. If the current total jump distance exceeds the target by an odd amount, it keeps moving forward one jump at a time. This process continues until the extra distance is an even number. When the extra part is even, it means a simple flip of one of the previous jumps will land the ball exactly on the target spot.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||
| WalkCCC | C++ | Python | Java | ||||||
| leetcode.ca | C++ | Python | JS | Java | Go | ||||
| LeetcodeHelp | C++ | Python | Java | ||||||
| Progiez | C++ | Python | Java | ||||||
| github | black-shadows | C++ | |||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| JoshCrozier | JS | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| lzl124631x | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| wisdompeak | C++ | ||||||||
| YuriSpiridonov | Python | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python | ||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||
| Progiez | C++, Java, Python | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| JoshCrozier | JavaScript | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| lzl124631x | C++ | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| wisdompeak | C++ | ||||||||
| YuriSpiridonov | Python |
Videos
Solved On The Same Day
- problem 764: Largest Plus Sign
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality