DDSA Solutions

476. Number Complement

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

Problem Overview

Flip all bits of the number but only up to its highest set bit.

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

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

Example Walkthrough

Input: num=5 (101)

  1. 1.len=3, mask=111=7.
  2. 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
C#
// 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?

Related Problems