3226. Number of Bit Changes to Make Two Integers Equal Solution

The problem

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.

Example 1:

Input: n = 13, k = 4

Output: 2

Explanation:
Initially, the binary representations of n and k are n = (1101)₂ and k = (0100)₂.
We can change the first and fourth bits of n. The resulting integer is n = (0100)₂ = k.

Example 2:

Input: n = 21, k = 21

Output: 0

Explanation:
n and k are already equal, so no changes are needed.

Example 3:

Input: n = 14, k = 13

Output: -1

Explanation:
It is not possible to make n equal to k.

Constraints:

1 <= n, k <= 10⁶

Approach overview

Problem Overview: Given two integers n and k, determine the minimum number of bit changes required to make them equal. The key constraint: you can only flip bits from 1 → 0. If k requires a bit that is 0 in n, the transformation is impossible.

Approach 1: Count Set Bit Differences (O(1) time, O(1) space)

This method compares the binary representation of both numbers using bitwise operations from bit manipulation. First check feasibility using (n & k) == k. This ensures every bit set in k is also set in n; otherwise you would need a 0 → 1 flip, which is not allowed. If the check passes, compute n ^ k to identify positions where bits differ. Every differing bit must be turned off in n. Count the set bits in this XOR result using a popcount operation. The number of set bits equals the required number of flips.

Approach 2: Direct Bit Count Comparison (O(1) time, O(1) space)

This version works directly at the bit level without relying entirely on XOR. Iterate through each bit position (usually up to 32 for standard integers) using shifts from bitwise operations. Extract the current bit of n and k with (x >> i) & 1. If a position has k = 1 but n = 0, the conversion cannot be done, so return -1. If n = 1 and k = 0, increment the change counter because that bit must be flipped off. Continue scanning all bit positions and return the total flips.

Both approaches rely on the same insight: only bits that are 1 in n but 0 in k need modification. Bit operations make the comparison extremely fast because integers have a fixed number of bits. These techniques are fundamental in problems involving masks, flags, and binary constraints, commonly grouped under bit manipulation.

Recommended for interviews: The XOR-based approach is usually expected. It shows strong familiarity with bitwise reasoning and produces a concise solution. The explicit bit iteration version is also acceptable and demonstrates understanding of how individual bits behave, but the XOR + popcount solution is shorter and more idiomatic.

Approach 1: Count Set Bit Differences

To find the number of bit changes needed to make n equal to k, calculate the XOR of n and k. The result will give a number where each '1' represents a position where n and k differ. Count how many '1s' are present in the bits of n & ~k because you can only change 1s to 0s in n.

Python

def bit_changes(n, k):
    diff = n ^ k
    if (k & ~n) != 0:
        return -1
    count = 0
    while diff:
        diff &= (diff - 1)
        count += 1
    return count

print(bit_changes(13, 4))  # Output: 2
print(bit_changes(21, 21)) # Output: 0
print(bit_changes(14, 13)) # Output: -1

Java

public class Main {
    public static int bitChanges(int n, int k) {
        int diff = n ^ k;
        if ((k & ~n) != 0) return -1;
        int count = 0;
        while (diff != 0) {
            diff &= (diff - 1);
            count++;
        }
        return count;
    }
    public static void main(String[] args) {
        System.out.println(bitChanges(13, 4));  // Output: 2
        System.out.println(bitChanges(21, 21)); // Output: 0
        System.out.println(bitChanges(14, 13)); // Output: -1
    }
}

C++

#include <iostream>
using namespace std;

int bit_changes(int n, int k) {
    int diff = n ^ k;
    if ((k & ~n) != 0) return -1;
    int count = 0;
    while (diff) {
        diff &= (diff - 1);
        count++;
    }
    return count;
}

int main() {
    cout << bit_changes(13, 4) << endl;  // Output: 2
    cout << bit_changes(21, 21) << endl; // Output: 0
    cout << bit_changes(14, 13) << endl; // Output: -1
    return 0;
}

JavaScript

function bitChanges(n, k) {
    let diff = n ^ k;
    if ((k & ~n) !== 0) return -1;
    let count = 0;
    while (diff !== 0) {
        diff &= (diff - 1);
        count++;
    }
    return count;
}

console.log(bitChanges(13, 4));  // Output: 2
console.log(bitChanges(21, 21)); // Output: 0
console.log(bitChanges(14, 13)); // Output: -1;

#include <stdio.h>

int bit_changes(int n, int k) {
    int diff = n ^ k;
    // Check if k has any bit set that n doesn't have
    if ((k & ~n) != 0) return -1;
    int count = 0;
    while (diff) {
        diff &= (diff - 1);
        count++;
    }
    return count;
}

int main() {
    printf("%d\n", bit_changes(13, 4));  // Output: 2
    printf("%d\n", bit_changes(21, 21)); // Output: 0
    printf("%d\n", bit_changes(14, 13)); // Output: -1
    return 0;
}

using System;

class Program {
    static int BitChanges(int n, int k) {
        int diff = n ^ k;
        if ((k & ~n) != 0) return -1;
        int count = 0;
        while (diff != 0) {
            diff &= (diff - 1);
            count++;
        }
        return count;
    }

    static void Main() {
        Console.WriteLine(BitChanges(13, 4));  // Output: 2
        Console.WriteLine(BitChanges(21, 21)); // Output: 0
        Console.WriteLine(BitChanges(14, 13)); // Output: -1
    }
}

Python's implementation leverages the same logic using XOR and checking bit differences. After establishing that n can be transformed to k, it counts the number of different bits using while loop driven by bit manipulation.

Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Direct Bit Count Comparison

Count the number of '1' bits in the binary representation of n and k. If k has more '1s' than n, it is impossible to transform n into k as we can only change 1s to 0s. Otherwise, the number of changes required is simply the difference in their respective '1' counts.

Python

def count_set_bits(x):
    count = 0
    while x:
        count += x & 1
        x >>= 1
    return count

def bit_changes(n, k):
    set_n = count_set_bits(n)
    set_k = count_set_bits(k)
    if set_k > set_n:
        return -1
    return set_n - set_k

print(bit_changes(13, 4))  # Output: 2
print(bit_changes(21, 21)) # Output: 0
print(bit_changes(14, 13)) # Output: -1

Java

public class Main {
    public static int countSetBits(int x) {
        int count = 0;
        while (x != 0) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }

    public static int bitChanges(int n, int k) {
        int setN = countSetBits(n);
        int setK = countSetBits(k);
        if (setK > setN) return -1;
        return setN - setK;
    }

    public static void main(String[] args) {
        System.out.println(bitChanges(13, 4));  // Output: 2
        System.out.println(bitChanges(21, 21)); // Output: 0
        System.out.println(bitChanges(14, 13)); // Output: -1
    }
}

C++

#include <iostream>
using namespace std;

int countSetBits(int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

int bitChanges(int n, int k) {
    int setN = countSetBits(n);
    int setK = countSetBits(k);
    if (setK > setN) return -1;
    return setN - setK;
}

int main() {
    cout << bitChanges(13, 4) << endl;  // Output: 2
    cout << bitChanges(21, 21) << endl; // Output: 0
    cout << bitChanges(14, 13) << endl; // Output: -1
    return 0;
}

JavaScript

function countSetBits(x) {
    let count = 0;
    while (x !== 0) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

function bitChanges(n, k) {
    let setN = countSetBits(n);
    let setK = countSetBits(k);
    if (setK > setN) return -1;
    return setN - setK;
}

console.log(bitChanges(13, 4));  // Output: 2
console.log(bitChanges(21, 21)); // Output: 0
console.log(bitChanges(14, 13)); // Output: -1;

#include <stdio.h>

int count_set_bits(int x) {
    int count = 0;
    while (x) {
        count += x & 1;
        x >>= 1;
    }
    return count;
}

int bit_changes(int n, int k) {
    int set_n = count_set_bits(n);
    int set_k = count_set_bits(k);
    if (set_k > set_n) return -1;
    return set_n - set_k;
}

int main() {
    printf("%d\n", bit_changes(13, 4));  // Output: 2
    printf("%d\n", bit_changes(21, 21)); // Output: 0
    printf("%d\n", bit_changes(14, 13)); // Output: -1
    return 0;
}

using System;

class Program {
    static int CountSetBits(int x) {
        int count = 0;
        while (x != 0) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }

    static int BitChanges(int n, int k) {
        int setN = CountSetBits(n);
        int setK = CountSetBits(k);
        if (setK > setN) return -1;
        return setN - setK;
    }

    static void Main() {
        Console.WriteLine(BitChanges(13, 4));  // Output: 2
        Console.WriteLine(BitChanges(21, 21)); // Output: 0
        Console.WriteLine(BitChanges(14, 13)); // Output: -1
    }
}

This Python implementation uses a helper function to determine the number of 1s in n and k. It ensures converting n to k is possible before calculating the needed changes.

Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Bit Manipulation

If the bitwise AND result of n and k is not equal to k, it indicates that there exists at least one bit where k is 1 and the corresponding bit in n is 0. In this case, it is impossible to modify a bit in n to make n equal to k, and we return -1. Otherwise, we count the number of 1s in the binary representation of n \oplus k.

The time complexity is O(log n), and the space complexity is O(1).

TypeScript

function minChanges(n: number, k: number): number {
    return (n & k) !== k ? -1 : bitCount(n ^ k);
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

func minChanges(n int, k int) int {
	if n&k != k {
		return -1
	}
	return bits.OnesCount(uint(n ^ k))
}

Rust

impl Solution {
    pub fn min_changes(n: i32, k: i32) -> i32 {
        if (n & k) != k {
            -1
        } else {
            (n ^ k).count_ones() as i32
        }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Count Set Bit Differences	Time Complexity: O(log n) Space Complexity: O(1)
Direct Bit Count Comparison	Time Complexity: O(log n) Space Complexity: O(1)
Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Count Set Bit Differences (XOR + Popcount)	O(1)	O(1)	Best general solution. Uses XOR to quickly identify differing bits and built-in bit counting.
Direct Bit Count Comparison	O(1)	O(1)	Useful when demonstrating manual bit inspection or when popcount utilities are unavailable.

Frequently asked questions

Is Number of Bit Changes to Make Two Integers Equal easy or hard?

The problem is classified as Easy because it requires basic bit manipulation concepts. Once you recognize that only 1→0 flips are allowed, the solution reduces to validating the bit pattern and counting differing bits using XOR.

Number of Bit Changes to Make Two Integers Equal Python/Java solution

In Python or Java, check feasibility with (n & k) == k. Then compute the differing bits using n ^ k and count them using built-in functions like bin(x).count('1') in Python or Integer.bitCount(x) in Java. This produces an O(1) time and O(1) space solution.

How to solve Number of Bit Changes to Make Two Integers Equal in O(1)?

Check if the transformation is possible using (n & k) == k. If this condition fails, return -1 because converting a 0 bit in n to 1 is not allowed. Otherwise compute diff = n ^ k and count the number of set bits in diff. Each set bit corresponds to a required 1→0 flip.

What is the best approach for Number of Bit Changes to Make Two Integers Equal?

The most efficient approach uses bit manipulation with XOR and a feasibility check. First verify that (n & k) == k to ensure no 0→1 flips are required. Then compute n ^ k and count the set bits. Each set bit represents a position where n must flip a 1 to 0. This runs in O(1) time and O(1) space for fixed-size integers.

Is Number of Bit Changes to Make Two Integers Equal asked at Google/Amazon/Meta?

Bit manipulation problems similar to this appear frequently in interviews at companies like Google, Amazon, and Meta. Interviewers use them to test understanding of binary representation, bit masks, and efficient bitwise operations. Variants often involve counting differing bits or validating bit constraints.

What data structure is used in Number of Bit Changes to Make Two Integers Equal?

The problem does not require complex data structures. It relies on bitwise operations on integers such as AND, XOR, shifts, and set-bit counting. These operations are core techniques in bit manipulation problems.

What is the time complexity of Number of Bit Changes to Make Two Integers Equal?

The optimal solution runs in O(1) time because integers have a fixed number of bits (typically 32). Operations such as bitwise AND, XOR, and popcount execute in constant time. Space complexity is also O(1) since only a few integer variables are used.

Number of Bit Changes to Make Two Integers Equal solution and explanation

The problem

Approach overview

Approach 1: Count Set Bit Differences

Approach 2: Direct Bit Count Comparison

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Number of Bit Changes to Make Two Integers Equal solution and explanation

The problem

Approach overview

Approach 1: Count Set Bit Differences

Approach 2: Direct Bit Count Comparison

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems