Minimum One Bit Operations to Make Integers Zero

Minimum One Bit Operations to Make Integers Zero - Problem

Given an integer n, you must transform it into 0 using the following operations any number of times:

Change the rightmost (0th) bit in the binary representation of n.
Change the ith bit in the binary representation of n if the (i-1)th bit is set to 1 and the (i-2)th through 0th bits are set to 0.

Return the minimum number of operations to transform n into 0.

Input & Output

Example 1 — Basic Case

$ Input: n = 3

› Output: 2

💡 Note: Binary 3 = 11. First operation: change rightmost bit → 10 (2). Second operation: change bit 1 since bit 0 is 0 → 00 (0). Total: 2 operations.

Example 2 — Single Bit

$ Input: n = 6

› Output: 4

💡 Note: Binary 6 = 110. Following the Gray code pattern: f(6) = 6 ⊕ f(3) = 6 ⊕ 2 = 110 ⊕ 010 = 100 = 4 operations.

Example 3 — Edge Case Zero

$ Input: n = 0

› Output: 0

💡 Note: Already at target 0, no operations needed.

Constraints

0 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Integer n in binary representation

Operations

Apply allowed bit flip operations

Target

Reach 0 with minimum operations

Key Takeaway

🎯 Key Insight: The problem follows Gray code pattern - use formula f(n) = n ⊕ f(n>>1) for O(log n) solution

Asked in

G Google 35 f Facebook 28 M Microsoft 22

The key insight is recognizing this follows the Gray code pattern where each number maps to its position in the inverse Gray code sequence. The optimal approach uses the mathematical formula f(n) = n ⊕ f(n>>1) achieving O(log n) time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n)	O(n)	Cache results of recursive calls to avoid recomputation
Recursive Brute Force	O(2ⁿ)	O(n)	Try all possible operations recursively until reaching 0
Gray Code Pattern Recognition	O(log n)	O(log n)	Recognize this follows Gray code sequence with mathematical formula

Memoized Recursion — Algorithm Steps

Use hash map to store computed results
Check cache before recursive call
Store result in cache before returning
Same logic as brute force but with memoization

Visualization

Tap to expand

Step-by-Step Walkthrough

Cache Miss

First encounter: compute and store result

Cache Hit

Subsequent encounters: return cached result

Efficiency

Each number computed only once

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>

#define HASH_SIZE 100003

typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

Node* hash_table[HASH_SIZE];

int hash_function(int key) {
    return (key % HASH_SIZE + HASH_SIZE) % HASH_SIZE;
}

void hash_put(int key, int value) {
    int index = hash_function(key);
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->next = hash_table[index];
    hash_table[index] = node;
}

int hash_get(int key) {
    int index = hash_function(key);
    Node* node = hash_table[index];
    while (node) {
        if (node->key == key) {
            return node->value;
        }
        node = node->next;
    }
    return -1;
}

int min(int a, int b) {
    return (a < b) ? a : b;
}

int helper(int num) {
    if (num == 0) return 0;
    
    int cached = hash_get(num);
    if (cached != -1) return cached;
    
    int minOps = INT_MAX;
    
    // Try flipping rightmost bit
    minOps = min(minOps, 1 + helper(num ^ 1));
    
    // Try flipping bit i if conditions are met
    for (int i = 1; i < 32; i++) {
        if ((1 << i) > num) break;
        // Check if bit i-1 is 1 and bits 0 to i-2 are all 0
        if ((num & (1 << (i-1))) && (num & ((1 << (i-1)) - 1)) == 0) {
            minOps = min(minOps, 1 + helper(num ^ (1 << i)));
        }
    }
    
    hash_put(num, minOps);
    return minOps;
}

int solution(int n) {
    memset(hash_table, 0, sizeof(hash_table));
    return helper(n);
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each unique number from 0 to n is computed at most once and cached

✓ Linear Growth

Space Complexity

O(n)

Hash map stores results for up to n different numbers plus recursion stack

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~35 min Avg. Time

847 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

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler