1009. Complement of Base 10 Integer

EasyView on LeetCode

Math Bit Manipulation

Time: O(log n)

Space: O(1)

Intuition

XOR with a mask of all 1s matching the bit length of n. Complement flips all bits in the representation.

Algorithm

1If n==0: return 1.
2Find bit length: mask = (1 << bitLength) - 1.
3Return n XOR mask.

Common Pitfalls

•n=0 is a special case. Mask size equals number of bits in n.

1009.cs

// Approach: Build a bitmask of all 1s with the same bit-length as n; XOR with n gives the complement.
// Time: O(log n) Space: O(1)

public class Solution
{
    public int BitwiseComplement(int n)
    {
        int mask = 1;
        while (mask < n)
            mask = (mask << 1) + 1;
            
        return mask ^ n;
    }
}

Was this solution helpful?