Integer Replacement - Practice Coding Problems

Integer Replacement - Problem

Given a positive integer n, you can apply one of the following operations:

If n is even, replace n with n / 2
If n is odd, replace n with either n + 1 or n - 1

Return the minimum number of operations needed for n to become 1.

Input & Output

Example 1 — Basic Case

$ Input: n = 8

› Output: 3

💡 Note: 8 is even → 8/2 = 4, then 4/2 = 2, then 2/2 = 1. Total: 3 operations.

Example 2 — Odd Number Choice

$ Input: n = 7

› Output: 4

💡 Note: 7 is odd → choose 7-1=6, then 6/2=3, then 3-1=2, then 2/2=1. Total: 4 operations.

Example 3 — Small Odd

$ Input: n = 3

› Output: 2

💡 Note: 3 is odd → choose 3-1=2 (better than 3+1=4), then 2/2=1. Total: 2 operations.

Constraints

1 ≤ n ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Start with positive integer n

Process

Apply operations: divide by 2 if even, add/subtract 1 if odd

Output

Return minimum operations to reach 1

Key Takeaway

🎯 Key Insight: Use bit patterns to choose optimal operations - add 1 when odd numbers end with '11' in binary to create more trailing zeros

Asked in

G Google 25 M Microsoft 18 F Facebook 15 a Amazon 12

The key insight is using bit manipulation to make optimal choices for odd numbers. When an odd number ends with '11' in binary, adding 1 creates more trailing zeros for faster division. The optimal approach uses greedy bit manipulation with Time: O(log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Bit Manipulation Greedy	O(log n)	O(1)	Use bit patterns to make optimal choices for odd numbers
Memoized Recursion	O(log n)	O(log n)	Cache results of subproblems to avoid redundant calculations
Recursive Brute Force	O(2^n)	O(log n)	Try all possible operations recursively without memoization

Bit Manipulation Greedy — Algorithm Steps

If n is even, divide by 2
If n is odd and ends with '11' in binary (except n=3), add 1
If n is odd and doesn't end with '11' in binary (or n=3), subtract 1
Count operations until reaching 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze Bits

For odd numbers, examine last 2 bits to decide +1 or -1

Optimal Choice

Choose operation that creates more trailing zeros

Result

Minimal operations through greedy bit manipulation

Code -

solution.c — C

#include <stdio.h>

int solution(int n) {
    int operations = 0;
    
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            // For odd numbers, check if adding 1 creates more trailing zeros
            // This happens when n & 3 == 3 (ends with '11' in binary)
            // Exception: n = 3, where subtracting 1 is better
            if (n == 3 || (n & 3) == 1) {
                n -= 1;
            } else {
                n += 1;
            }
        }
        operations += 1;
    }
    
    return operations;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int result = solution(n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Each operation reduces n by roughly half, so we need at most log n operations

⚡ Linearithmic

Space Complexity

O(1)

Only uses a few variables, no extra data structures or recursion stack

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Bit Manipulation Greedy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler