DDSA Solutions

1009. Complement of Base 10 Integer

EasyView on LeetCode
MathBit Manipulation
Time: O(log n)
Space: O(1)

Problem Overview

XOR with a mask of all 1s matching the bit length of n.

Intuition

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

Algorithm

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

Common Pitfalls

  • •n=0 is a special case. Mask size equals number of bits in n.
1009.cs
C#
// 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?

Related Problems