LeetCode Entry

191. Number of 1 Bits

29.11.2023 easy 2023 kotlin

Bits count

191. Number of 1 Bits easy blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/420

Problem TLDR

Bits count

Intuition

The optimal solution would be using built-in n.countOneBits().

However, there is a knonw technique using tabulation DP to count bits. The recurrence is: count(n) = count(n « 1) + 1?1:0. For example, count(1111) = 1 + count(111). Or, count(110) = 0 + count(11)

Approach

  • carefult with the table size, it must be 2^8=256

Complexity

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

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

Code


  val dp = IntArray(256).apply {
    for (i in 1..<size)
      this[i] = this[i / 2] + (i and 1)
  }
  fun hammingWeight(n:Int):Int =
    dp[n and 255] +
    dp[(n ushr 8) and 255] +
    dp[(n ushr 16) and 255] +
    dp[(n ushr 24) and 255]