The Reach a Number problem asks for the minimum number of steps to reach exactly target from 0, where step k moves ±k. You choose the direction (+ or -) for each step. This coding problem uses math: find the minimum n such that 1+2+...+n ≥ |target| and (n*(n+1)/2 - |target|) is even (can flip a subset of steps). The math and binary search interview pattern is demonstrated.
InMobi, Microsoft, Meta, Amazon, Google, and Bloomberg ask this because the elegant mathematical solution — finding the right n using the parity condition — avoids BFS on an infinite state space. It tests the ability to derive mathematical insight from the problem structure.
Mathematical observation. Target becomes |target| (symmetric). Find minimum n where S = n*(n+1)/2 ≥ |target| AND (S - |target|) % 2 == 0. The even condition ensures we can flip some positive steps to negative to hit the exact target. Find this n using binary search or linear scan from ceil(sqrt(2*target)).
target=3. n=2: S=3=3 ✓. (3-3)=0 even ✓. Return 2 (steps: +1+2=3). target=2. n=2: S=3. (3-2)=1 odd ✗. n=3: S=6. (6-2)=4 even ✓. Return 3 (steps: +1+2-3? No: -1+3=2... +1-2+3=2✓). 3 steps. target=5. n=3: S=6. (6-5)=1 odd ✗. n=4: S=10. (10-5)=5 odd ✗. n=5: S=15. (15-5)=10 even ✓. Return 5.
Reach a Number teaches that many "minimum steps" problems have mathematical shortcuts. The parity trick: if you need to reduce S to target, flip a subset of steps (costing -2k each flip). So S - target must be even. Once you identify this, binary search or linear scan for the minimum n is O(log n). Practice mathematical step problems: "jump game IV," "minimum jumps to reach target." Always ask: can a formula replace BFS?
