Problem 754

Abstract / Summary

You start at 0 and can move by adding or subtracting 1 2 3 4 5 each turn trying to reach a target number.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
14 lines | 356 bytes | submitted September 21, 2023 | GitHub   9% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 44% (100k+ submissions).

Typical patterns to solve this problem:
  • Binary Search
  • Math
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 6.41 | σ = 1.64

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
30 links | 17 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

1 medium
2 solutions   September 21, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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