💥💥 Beats 100% on runtime and memory [EXPLAINED]
IntuitionWe have to count the number of set bits (1s) in a number efficiently. A direct approach would be too slow, so I used dynamic programming (via memoizati
# Intuition
We have to count the number of set bits (1s) in a number efficiently. A direct approach would be too slow, so I used dynamic programming (via memoization) to store and reuse results for previously calculated numbers. This way, I didn’t have to recompute the same values multiple times, which greatly improves performance.

# Approach
I calculated the number of set bits using a helper function with memoization to store previous results, combined binary search for efficiency in determining the maximum number, and used a simple loop to calculate the total sum of bits.

# Complexity
- Time complexity:
O(log n) for most operations, as we work with bits, and each step involves halving the problem size using binary search.

- Space complexity:
O(n) due to the memoization storage for the number of set bits for numbers up to n.

# Code
```kotlin []
class Solution {
    private val dp = mutableMapOf<Long, Long>()
    
    private fun power(n: Long, expo: Long, mod: Long): Long {
        var ans = 1L
        var base = n
        var exp = expo
        
        while (exp > 0) {
            if (exp % 2 != 0L) {
                ans = (ans * base) % mod
            }
            base = (base * base) % mod
            exp /= 2
        }
        
        return ans
    }
    
    private fun getNumBits(n: Long): Long {
        if (n == 0L) return 0L
        dp[n]?.let { return it }
        
        var ans = 0L
        var num = n + 1
        
        for (i in 60 downTo 0) {
            if ((1L shl i) < num) {
                ans = getNumBits((1L shl i) - 1)
                val rem = num - (1L shl i)
                ans += getNumBits(rem - 1) + rem
                break
            }
        }
        
        dp[n] = ans
        return ans
    }
    
    private fun getMaxNum(n: Long): Long {
        var left = 1L
        var right = 1e15.toLong()
        var ans = 0L
        
        while (left <= right) {
            val mid = (left + right) / 2
            val placesOccupied = getNumBits(mid)
            
            if (placesOccupied <= n) {
                ans = mid
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return ans
    }
    
    private fun getSum(n: Long): Long {
        var res = 0L
        
        for (i in 1 until 50) {
            val blockSize = 1L shl (i + 1)
            val onesInBlock = blockSize / 2
            val completeBlocks = n / blockSize
            res += completeBlocks * onesInBlock * i
            
            val rem = n % blockSize
            res += maxOf(0L, rem + 1 - onesInBlock) * i
        }
        
        return res
    }
    
    private fun func(n: Long): Long {
        if (n == 0L) return 0L
        
        val maxNum = getMaxNum(n)
        val placesOccupied = getNumBits(maxNum)
        var ans = getSum(maxNum)
        
        var remaining = n - placesOccupied
        var maxNumPlusOne = maxNum + 1
        
        for (i in 0 until 64) {
            if (maxNumPlusOne and (1L shl i) != 0L) {
                remaining--
                ans += i
            }
            if (remaining <= 0) break
        }
        
        return ans
    }
    
    fun solve(query: LongArray): Int {
        val (L, R, mod) = query
        return (power(2, func(R + 1) - func(L), mod) % mod).toInt()
    }

    fun findProductsOfElements(queries: Array<LongArray>): IntArray {
        return queries.map { solve(it) }.toIntArray()
    }
}

```
['Array', 'Math', 'Binary Search', 'Dynamic Programming', 'Bit Manipulation', 'Simulation', 'Binary Tree', 'Bitmask', 'Kotlin']