476. Number Complement

Time: O(log n)

Space: O(1)

Intuition

Flip all bits of the number but only up to its highest set bit. Create a mask of all 1s up to that bit length, then XOR.

Algorithm

1Find bit length: len = floor(log2(num)) + 1.
2Create mask = (1 << len) - 1.
3Return num XOR mask.

Example Walkthrough

Input: num=5 (101)

1.len=3, mask=111=7.
2.5 XOR 7 = 010 = 2.

Output: 2

Common Pitfalls

•Do not flip leading zeros — only bits within the number's bit length.

476.cs

// Approach: XOR the number bit by bit with 1 up to and including its
// highest set bit to flip all relevant bits.
// Time: O(log n) Space: O(1)

public class Solution
{
    public int FindComplement(int num)
    {
        for (long i = 1; i <= num; i <<= 1)
            num ^= (int)i;

        return num;
    }
}

Was this solution helpful?