Number of Bit Changes to Make Two Integers Equal

Number of Bit Changes to Make Two Integers Equal - Problem

Bit Manipulation Easy

You are given two positive integers n and k.

You can choose any bit in the binary representation of n that is equal to 1 and change it to 0.

Return the number of changes needed to make n equal to k. If it is impossible, return -1.

Input & Output

Example 1 — Basic Case

$ Input: n = 13, k = 9

› Output: 1

💡 Note: n = 1101₂, k = 1001₂. Only bit 2 differs (1→0), so 1 change needed.

Example 2 — Impossible Case

$ Input: n = 9, k = 13

› Output: -1

💡 Note: n = 1001₂, k = 1101₂. Bit 2 needs to change from 0→1, which is impossible.

Example 3 — Already Equal

$ Input: n = 5, k = 5

› Output: 0

💡 Note: n and k are already equal, no changes needed.

Constraints

1 ≤ n, k ≤ 10⁶
n and k are positive integers

Visualization

Tap to expand

Understanding the Visualization

Input

Two integers n=13 and k=9

Process

Find bits that need to change from 1 to 0

Output

Count of required bit changes

Key Takeaway

🎯 Key Insight: Use XOR to find different bits and validate that we only turn OFF bits (1→0)

Asked in

M Microsoft 25 G Google 20 a Amazon 15

The key insight is that we can only turn bits OFF (1→0), never ON (0→1). Use XOR to find different bits and validate with (n & k) == k. Best approach uses bit manipulation: Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Bit-by-Bit Comparison	O(log n)	O(1)	Check each bit position individually and count required changes
XOR Bit Manipulation	O(log n)	O(1)	Use XOR to find different bits and validate the transformation

Bit-by-Bit Comparison — Algorithm Steps

Iterate through each bit position from 0 to 31
Compare bits at each position using bit masks
Count positions where n=1 and k=0
Return -1 if any position has n=0 and k=1

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Bits

Check each bit position from right to left

Count Changes

Count positions where n=1 and k=0

Validate

Return -1 if impossible (n=0, k=1)

Code -

solution.c — C

#include <stdio.h>

int solution(int n, int k) {
    int changes = 0;
    
    // Check each bit position
    for (int i = 0; i < 32; i++) {
        int nBit = (n >> i) & 1;
        int kBit = (k >> i) & 1;
        
        if (nBit == 1 && kBit == 0) {
            changes++;
        } else if (nBit == 0 && kBit == 1) {
            return -1;
        }
    }
    
    return changes;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(log n)

We check each bit position, at most 32 iterations for 32-bit integers

⚡ Linearithmic

Space Complexity

O(1)

Only using a few integer variables for counting and bit operations

✓ Linear Space

21.3K Views

Medium Frequency

~10 min Avg. Time

850 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-by-Bit Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler