LeetCode Entry

201. Bitwise AND of Numbers Range

21.02.2024 medium 2024 kotlin rust

Bitwise AND for [left..right].

201. Bitwise AND of Numbers Range medium blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/514

Problem TLDR

Bitwise AND for [left..right].

Intuition

To understand the problem, let’s observe how this works:

    // 0  0000
    // 1  0001           2^0
    // 2  0010
    // 3  0011
    // 4  0100 3..4 = 0  2^2
    // 5  0101 3..5 = 0
    // 6  0110
    // 7  0111 6..7
    // 8  1000           2^3
    // 9  1001  7..9 = 0

Some observations:

  • When interval intersects 4, 8 and so on, it AND operation becomes 0.
  • Otherwise, we take the common prefix: 6: 0110 & 7: 0111 = 0110.

Approach

We can take the most significant bit and compare it. In another way, we can just find the common prefix trimming the bits from the right side.

Complexity

  • Time complexity: \(O(1)\), at most 32 calls happens

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

Code


  fun rangeBitwiseAnd(left: Int, right: Int): Int {
    if (left == right) return left
    val l = left.takeHighestOneBit()
    val r = right.takeHighestOneBit()
    return if (l != r) 0 else
      l or rangeBitwiseAnd(left xor l, right xor r)
  }



  pub fn range_bitwise_and(left: i32, right: i32) -> i32 {
    if left == right { left }
    else { Self::range_bitwise_and(left / 2, right / 2) * 2 }
  }