Prime Number of Set Bits in Binary Representation

This solution for easy LC problem is very concise the easy to understand don’t you think?

class Solution {    
    val isPrime: (Int) -> Boolean = { num ->
        !(2..num/2).any { num % it == 0 }        
    }
    
    fun countPrimeSetBits(L: Int, R: Int): Int {
        var sum = 0
        for(i in L..R){
            val candidate = Integer.bitCount(i)
            sum += if(candidate > 1 && isPrime(candidate)) 1 else 0
        }
        return sum
    }
}
Runtime: 204 ms, faster than 20.00% of Kotlin online submissions for Prime Number of Set Bits in Binary Representation.
Memory Usage: 32.7 MB, less than 100.00% of Kotlin online submissions for Prime Number of Set Bits in Binary Representation.

We loop through from L to R (inclusive) and for each number, we count the number of set bits using Integer.bitCount() and then we check if the number of bits is a prime number.

comments powered by Disqus