29.11.2023
191. Number of 1 Bits easy
blog post
youtube
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 known 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
careful 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]