Coding questions · Salesforce

Minimize steps to reduce integer

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 (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.

Minimize Steps to Reduce Integer

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

Example 1

Input: (1,)
Output: 0

Explanation: n is already 1, so no steps are needed.

Example 2

Input: (2,)
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.