Minimize steps to reduce integer
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a positive integer n (1 <= n <= 2^61 -
1), in one step you may replace n with n/2 if n is even, or with n+1 or n-1 if n is odd. Return the minimum number of steps to reduce n to 1. Explain your algorithm, justify how you decide between n+1 and n-1 for odd n, and analyze time complexity.
Quick Answer: This question evaluates algorithm design skills and proficiency with integer operations and decision-making under parity constraints, testing competencies such as bitwise reasoning, greedy and dynamic-programming intuition, and complexity analysis.
Given a positive integer n, reduce it to 1 using the minimum possible number of steps. In one step, you may replace n with n / 2 if n is even, or replace n with either n + 1 or n - 1 if n is odd. Return the minimum number of steps required.
For odd numbers, the key decision is whether to increment or decrement. Except for n = 3, choose the operation that makes the result divisible by a larger power of 2. Practically, if n % 4 == 1, decrement n; if n % 4 == 3, increment n. The special case n = 3 should decrement to 2 because 3 -> 2 -> 1 takes 2 steps, while 3 -> 4 -> 2 -> 1 takes 3 steps.
Constraints
- 1 <= n <= 2^61 - 1
- Each operation must be one of: divide by 2 when even, add 1 when odd, or subtract 1 when odd
Examples
Input: (1,)
Expected Output: 0
Explanation: n is already 1, so no steps are needed.
Input: (2,)
Expected Output: 1
Explanation: 2 is even, so divide by 2: 2 -> 1.
Hints
- For an odd number, compare what happens after choosing n - 1 versus n + 1. Which one creates more trailing zero bits in binary?
- There is one important exception to the n % 4 rule: handle n = 3 separately.