Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Google SWE interview with a bit-manipulation flavored DP problem. The follow-up on the greedy rule for odd numbers is where things got interesting and also where I felt least confident.

Questions Asked (1)

Given a positive integer n, find the minimum number of operations to reduce it to 1. Each operation lets you divide by 2 if n is even, or increment/decrement by 1 if n is odd. What's the optimal greedy strategy for odd numbers, and how do you derive it from the last two bits?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I got the basic idea fast enough: halve when even, and for odd just pick whichever of n+1 or n-1 gets you to a better state faster.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by explaining the greedy strategy for odd numbers: if n % 4 == 1, decrement; if n % 4 == 3, increment (except when n == 3, then decrement). Then derive this from the last two bits: for odd n, the last two bits are either 01 (≡1 mod 4) or 11 (≡3 mod 4), and the choice ensures the next division by 2 yields an even number, minimizing future operations. Finally, discuss the algorithm's time complexity and edge cases.

Pro tip: Mention that the greedy choice is optimal because it maximizes the number of trailing zeros after the next division, and handle n=3 as a special case to avoid an extra operation.

1. Restate the problem and define operations

Clearly state the problem: given a positive integer n, reduce it to 1 using divide-by-2 (if even) and increment/decrement (if odd). Emphasize that we want the minimum number of operations.

2. Propose the greedy strategy for odd numbers

For odd n, if n % 4 == 1, decrement; if n % 4 == 3, increment (except n == 3, decrement). Explain that this choice aims to make the number divisible by 4, so after the next division by 2, the result is even, allowing more divisions.

3. Derive the strategy from the last two bits

Show that for odd n, the last two bits are either 01 (n ≡ 1 mod 4) or 11 (n ≡ 3 mod 4). If 01, decrementing changes the last two bits to 00, making it divisible by 4; if 11, incrementing changes to 00 (with carry), also divisible by 4. This maximizes trailing zeros after the next division.

4. Discuss optimality and edge cases

Argue that the greedy choice is optimal because it minimizes the number of operations by ensuring the next number is even and as large as possible in terms of divisibility by 2. Mention the special case n=3: incrementing gives 4 → 2 → 1 (3 ops), while decrementing gives 2 → 1 (2 ops), so decrement is better.

5. Analyze complexity and conclude

State that the algorithm runs in O(log n) time since each division by 2 halves the number, and O(1) space. Conclude that the greedy strategy is simple and efficient.

Key Points to Mention

Greedy strategy: for odd n, if n % 4 == 1, decrement; if n % 4 == 3, increment (except n=3).
Derivation from last two bits: 01 → decrement to 00; 11 → increment to 00 (with carry).
Optimality: maximizes trailing zeros after next division, reducing future operations.
Special case n=3: decrement is better than increment.
Time complexity O(log n) and space O(1).
Alternative approach: dynamic programming or BFS to verify greedy, but greedy is optimal.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.