How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Salesforce.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Salesforce during technical interviews.

Minimize steps to reduce integer | Salesforce Coding Question

Quick Overview

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.

Quick Overview

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.

Input: (3,)

Expected Output: 2

Explanation: The best path is 3 -> 2 -> 1. Incrementing first would take 3 steps: 3 -> 4 -> 2 -> 1.

Input: (8,)

Expected Output: 3

Explanation: Repeatedly divide by 2: 8 -> 4 -> 2 -> 1.

Input: (7,)

Expected Output: 4

Explanation: One optimal path is 7 -> 8 -> 4 -> 2 -> 1, which takes 4 steps.

Input: (15,)

Expected Output: 5

Explanation: The best path is 15 -> 16 -> 8 -> 4 -> 2 -> 1, which takes 5 steps.

Input: (2305843009213693951,)

Expected Output: 62

Explanation: This is 2^61 - 1. Increment once to get 2^61, then divide by 2 exactly 61 times.

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.

Last updated: Jun 25, 2026

Loading coding console...