LeetCode Entry

476. Number Complement

22.08.2024 easy 2024 kotlin rust

Invert bits: 101 becomes 010 manipulation

476. Number Complement easy blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/710

Problem TLDR

Invert bits: 101 becomes 010 #easy #bit_manipulation

Intuition

One way to do it is inverting all bits and then applying some mask to trim the bits to the left:


0000 0000  0000 0000  0000 0000  0000 0101    5
0000 0000  0000 0000  0000 0000  0000 0100    5.takeHighestOneBit()
0000 0000  0000 0000  0000 0000  0000 1000    5.takeHighestOneBit() shl 1
0000 0000  0000 0000  0000 0000  0000 0111    (5.takeHighestOneBit() shl 1) - 1

Now we can use that mask for (~a&mask) or just a ^ mask.

Approach

  • Rust has leading_zeros()
  • There is a cool trick to paint the bits to make the mask: a >> 1 | a, a >> 2 | a, a >> 4 | a, a >> 8 | a, a >> 16 | a.

Complexity

  • Time complexity: \(O(1)\)

  • Space complexity: \(O(1)\)

Code


    fun findComplement(num: Int) =
        num xor ((num.takeHighestOneBit() shl 1) - 1)



    pub fn find_complement(num: i32) -> i32 {
        num ^ ((1 << (32 - num.leading_zeros())) - 1)
    }