LeetCode #754: Reach a Number, Sum Until the Parity Fits

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: start at 0. On move i you step i units left or right. Return the fewest moves needed to land on target. Brute force: a BFS over every reachable position grows exponentially. The key insight: by symmetry, use the absolute value of target. Add 1 + 2 + … + k until the sum is at least target. Flipping step j from right to left takes 2j off the sum, so the leftover difference has to be even. Keep adding steps until sum − target is even. That takes at most 2 extra steps. Dry run: with target = 2, 1 + 2 = 3 leaves a difference of 1, which is odd. 1 + 2 + 3 = 6 leaves 4, which is even, so flip the 2: 1 − 2 + 3 = 2. The answer is 3. Complexity: O(√target) time and O(1) space. Problem: https://leetcode.com/problems/reach-a... Related: Broken Calculator (991), Minimum Moves to Reach Target Score (2139), Arranging Coins (441) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode754 #reachanumber #math #parity #greedy #binarysearch #medium #coding #codinginterview #dsa #python #amazon #faang #brutetobest