Given an integer n, you may perform only the following operations:
- If n is divisible by 2, you may perform:
n = n / 2 - You may increment n by 1:
n = n + 1
Your goal is to compute the smallest number of operations required to reduce n to 1.
Example:
n = 1
→ output = 0这题是 Tesla 的经典思维题，重点不在代码，而在你能不能想出一个 最优策略 。
题目给你的操作只有两个：
- 偶数 ：能除 2 就立刻除，这是最优的。
- 奇数 ：只能变成
n+1（但等价地也能往下掉到n-1）。
核心难点是：
奇数到底什么时候 +1，什么时候 -1？
规律来自 二进制 ：
- 如果奇数
n的二进制末尾是…111（比如 7 = 111，15 = 1111）
→ 加 1 后会形成很多结尾 0，之后可以连续除 2，很赚 - 如果末尾不是那种情况
→ 直接走n-1会更快
特例：n = 3 必须走 3 → 2 → 1，不能 3 → 4 → 2 → 1（多一步）。
整个算法只需 O(log n)，面试官考点就是：
你能否根据 二进制结构 做出正确的贪心判断，而不是暴力 BFS。
VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Tesla、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Tiktok 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。
正文完
