Problem statement

https://binarysearch.com/problems/Set-Bits/

Solution

We can use recursion here: if we have say n = 100100, then we can look at 10010 and calculate answer from it. Here we need to count number of one bits in prefix as well and I do it with bit count, which is O(log n). If needed we can make it in O(log n) for all prefixes, but it is fast enough like this.

Complexity

It is O(log^2n) for time and O(log n) for space.

Code

class Solution:
    def solve(self, n):
        if n == 1: return 1
        return self.solve(n//2) * 2 + (n+1)//2 - ((n+1)%2) * bin(n).count("1")