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 Onsite 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 operations to reduce integer to zero

Company: Salesforce

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a non-negative integer `n`. In **one operation**: - If `n` is even, you may replace `n` with `n / 2`. - If `n` is odd, you may replace `n` with either `n + 1` or `n - 1`. Return the **minimum number of operations** needed to make `n = 0`. ### Input - A single integer `n`. ### Output - An integer: the minimum number of operations to reach `0`. ### Constraints - Assume `0 <= n <= 10^9` (or similar large bound). ### Examples - `n = 0` → `0` - `n = 7` → `5` (one optimal path: 7→8→4→2→1→0)

Quick Answer: This question evaluates algorithmic problem-solving and integer-manipulation skills, specifically assessing the ability to reason about operation counts and binary behavior, and it belongs to the Coding & Algorithms category.

You are given a non-negative integer `n`. In **one operation**: - If `n` is even, you may replace `n` with `n / 2`. - If `n` is odd, you may replace `n` with either `n + 1` or `n - 1`. Return the **minimum number of operations** needed to make `n = 0`. ### Examples - `n = 0` -> `0` (already zero) - `n = 3` -> `3` (3 -> 2 -> 1 -> 0) - `n = 7` -> `5` (7 -> 8 -> 4 -> 2 -> 1 -> 0) ### Constraints - `0 <= n <= 10^9`

Constraints

0 <= n <= 10^9
n fits in a 32-bit signed integer (and n+1 stays within range for the given bound)

Examples

Input: 0

Expected Output: 0

Explanation: n is already 0, so no operations are needed.

Input: 1

Expected Output: 1

Explanation: 1 is odd: 1 -> 0 by subtracting 1. One operation.

Input: 2

Expected Output: 2

Explanation: 2 -> 1 (halve) -> 0 (subtract 1). Two operations.

Input: 3

Expected Output: 3

Explanation: Special case: subtract first. 3 -> 2 -> 1 -> 0 uses 3 ops, beating 3 -> 4 -> 2 -> 1 -> 0 which uses 4.

Input: 6

Expected Output: 4

Explanation: 6 -> 3 (halve) -> 2 -> 1 -> 0. Four operations.

Input: 7

Expected Output: 5

Explanation: 7 is '111'; add 1 to carry through the run: 7 -> 8 -> 4 -> 2 -> 1 -> 0. Five operations.

Input: 8

Expected Output: 4

Explanation: A pure power of two: 8 -> 4 -> 2 -> 1 -> 0. Four operations.

Input: 15

Expected Output: 6

Explanation: 15 is '1111'; add 1: 15 -> 16 -> 8 -> 4 -> 2 -> 1 -> 0. Six operations.

Input: 35

Expected Output: 8

Explanation: 35 is '100011'; clearing the trailing run and halving yields 8 operations.

Input: 1023

Expected Output: 12

Explanation: 1023 is ten trailing ones; +1 carries to 1024 (2^10), then ten halvings to 1 and a final -1: 12 operations.

Input: 1000000000

Expected Output: 39

Explanation: Large boundary value; the greedy bit strategy reaches 0 in 39 operations, matching the BFS shortest path.

Hints

When n is even, halving is never worse than anything else, because it removes a factor of 2 in a single move and never increases the number of set bits.
When n is odd you must spend one operation to make it even, choosing +1 or -1. Think about which choice removes more 1-bits overall.
Look at the lowest two bits. If they are '11' (a run of trailing ones), adding 1 carries through the whole run and clears it, which usually wins - but n = 3 ('11') is the one exception where subtracting is better, since 3 -> 2 -> 1 -> 0 (3 ops) beats 3 -> 4 -> 2 -> 1 -> 0 (4 ops).

Quick Overview

This question evaluates algorithmic problem-solving and integer-manipulation skills, specifically assessing the ability to reason about operation counts and binary behavior, and it belongs to the Coding & Algorithms category.