Why do we take the absolute value of the target in Reach a Number?

Taking the absolute value leverages the symmetry of the number line, reducing the problem to a positive target while preserving the correct minimal move calculation.

How does binary search optimize finding the minimum moves?

Binary search narrows the candidate move count efficiently by checking cumulative sums, avoiding linear iteration and quickly locating the smallest valid number of steps.

What happens if the cumulative sum minus target is odd?

If the difference is odd, you cannot flip any subset of moves to reach the target exactly, so additional moves are required until the difference becomes even.

Can this approach handle negative targets?

Yes, by normalizing the target to its absolute value, the algorithm works identically due to symmetry, ensuring minimal move calculation is correct for all integers.

What is the key pattern exploited in Reach a Number?

The problem leverages the pattern that the sum of the first n integers must exceed the target and the excess must be even, allowing flipping moves to hit the exact target.

#754

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

到达终点数字

在一根无限长的数轴上，你站在 0 的位置。终点在 target 的位置。你可以做一些数量的移动 numMoves : 每次你可以选择向左或向右移动。第 i 次移动（从 i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。给定整数 target ，返回到达目标所需…

数学二分查找

题目描述

在一根无限长的数轴上，你站在0的位置。终点在target的位置。

你可以做一些数量的移动 numMoves :

每次你可以选择向左或向右移动。
第 i 次移动（从 i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。

给定整数 target ，返回 到达目标所需的最小移动次数(即最小 numMoves ) 。

示例 1:

输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。

示例 2:

输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。

提示:

-10⁹ <= target <= 10⁹
target != 0

lightbulb

解题思路

方法一：数学分析

由于对称性，每次可以选择向左或向右移动，因此，我们可以将 $\textit{target}$ 统一取绝对值。

定义 $s$ 表示当前所处的位置，用变量 $k$ 记录移动的次数。初始时 $s$ 和 $k$ 均为 $0$ 。

我们将 $s$ 一直循环累加，直到满足 $s\ge \textit{target}$ 并且 $(s-\textit{target}) \bmod 2 = 0$ ，此时的移动次数 $k$ 就是答案，直接返回。

为什么？因为如果 $s\ge \textit{target}$ 且 $(s-\textit{target})\mod 2 = 0$ ，我们只需要把前面 $\frac{s-\textit{target}}{2}$ 这个正整数变为负数，就能使得 $s$ 与 $\textit{target}$ 相等。正整数变负数的过程，实际上是将移动的方向改变，但实际移动次数仍然不变。

时间复杂度 $O(\sqrt{\left | \textit{target} \right | })$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)
        s = k = 0
        while 1:
            if s >= target and (s - target) % 2 == 0:
                return k
            k += 1
            s += k

speed

复杂度分析

指标	值
时间	O(\sqrt{\text{target}})
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Ask why the cumulative sum minus target parity matters for valid sequences.
question_mark
Probe if the candidate considers both positive and negative targets efficiently.
question_mark
Check if they identify the quadratic growth of sums and optimize using binary search instead of linear iteration.

warning

常见陷阱

外企场景

error
Ignoring the parity condition can lead to incorrect minimal move counts.
error
Attempting a linear search over moves without exploiting cumulative sum patterns wastes time.
error
Failing to normalize the target can cause redundant calculations for negative positions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the minimal moves to reach multiple targets simultaneously using the same incremental move pattern.
arrow_right_alt
Compute the number of distinct sequences of moves that reach the target with minimal steps.
arrow_right_alt
Extend to restricted moves where certain step sizes are forbidden, requiring adjustments in the binary search.

help

常见问题

外企场景

继续练习

#793 阶乘函数后 K 个零 #710 黑名单中的随机数 #668 乘法表中第k小的数