Scale Engineer

Number of Bit Changes to Make Two Integers Equal

Easy
#2865Time: O(log(max(n, k))). The length of the binary representation of a number `x` is proportional to `log(x)`. String operations like conversion and padding take time proportional to this length.Space: O(log(max(n, k))) to store the binary string representations of `n` and `k`.1 company
Patterns
Bit Manipulation
Companies
ThoughtWorks

Prompt

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)2 and k = (0100)2.
We can change the first and fourth bits of n. The resulting integer is n = (0100)2 = 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 <= 106

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves converting both integers n and k into their binary string representations. After ensuring both strings have the same length by padding the shorter one with leading zeros, we can iterate through them character by character to check for the conditions of the problem.

Algorithm

  • Convert n and k to binary strings, nStr and kStr.
  • Determine the maximum length between nStr and kStr.
  • Pad the shorter string with leading zeros to match the maximum length.
  • Initialize a changes counter to 0.
  • Iterate through the strings from i = 0 to length - 1.
  • At each position i, compare nStr.charAt(i) and kStr.charAt(i).
  • If nStr.charAt(i) == '0' and kStr.charAt(i) == '1', return -1.
  • If nStr.charAt(i) == '1' and kStr.charAt(i) == '0', increment changes.
  • After the loop, return changes.

Walkthrough

The core idea is to work with the numbers as text.

  1. First, we obtain the binary strings for n and k using Integer.toBinaryString().
  2. The binary strings might have different lengths. To compare them bit by bit, we need to align them. We find the maximum length and pad the shorter string with leading '0's until it matches the maximum length.
  3. We then iterate through the aligned strings from left to right (most significant to least significant bit).
  4. For each position i, we compare the characters n_str.charAt(i) and k_str.charAt(i).
    • If n has a '0' where k has a '1', the transformation is impossible, as we cannot change a '0' to a '1'. We return -1 immediately.
    • If n has a '1' where k has a '0', this is a required change. We increment a counter.
    • If the bits are the same, no action is needed.
  5. If the loop completes without finding an impossible case, the final value of the counter is our answer.
class Solution {    public int minChanges(int n, int k) {        String nStr = Integer.toBinaryString(n);        String kStr = Integer.toBinaryString(k);         int nLen = nStr.length();        int kLen = kStr.length();        int maxLen = Math.max(nLen, kLen);         // Pad with leading zeros to make lengths equal        while (nStr.length() < maxLen) {            nStr = "0" + nStr;        }        while (kStr.length() < maxLen) {            kStr = "0" + kStr;        }         int changes = 0;        for (int i = 0; i < maxLen; i++) {            char nBit = nStr.charAt(i);            char kBit = kStr.charAt(i);             if (nBit == '0' && kBit == '1') {                return -1; // Impossible to change 0 to 1            }            if (nBit == '1' && kBit == '0') {                changes++; // Required change from 1 to 0            }        }        return changes;    }}

Complexity

Time

O(log(max(n, k))). The length of the binary representation of a number `x` is proportional to `log(x)`. String operations like conversion and padding take time proportional to this length.

Space

O(log(max(n, k))) to store the binary string representations of `n` and `k`.

Trade-offs

Pros

  • Conceptually straightforward, especially for those more comfortable with string manipulation than bitwise operations.

Cons

  • Inefficient due to the overhead of string creation, concatenation (for padding), and character-by-character access.

  • The implementation is more verbose compared to bitwise solutions.

Solutions

class Solution {public  int minChanges(int n, int k) {    return (n & k) != k ? -1 : Integer.bitCount(n ^ k);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem