Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n. Examples:
Input: n = 3 Output: 4 Binary representations are 1, 2 and 3 1, 10 and 11 respectively. Total set bits are 1 + 1 + 2 = 4. Input: n = 6 Output: 9 Input: n = 7 Output: 12 Input: n = 8 Output: 13
We have existing solution for this problem please refer Count total set bits in all numbers from 1 to n link. We can solve this problem in python using map() function. Approach is very simple,
- Write a function which first converts number into binary using bin(num) function and returns count of set bits in it.
- Map user defined function on list of numbers from 1 to n and we will get list of individual count of set bits in each number.
- Sum up count of all set bits.
Python3
# Function to Count total set bits in all numbers# from 1 to n# user defined functiondef countSetBit(num): # convert decimal value into binary and # count all 1's in it binary = bin(num) return len([ch for ch in binary if ch=='1'])# function which count set bits in each numberdef countSetBitAll(input): # map count function on each number print (sum(map(countSetBit,input)))# Driver programif __name__ == "__main__": n = 8 input=[] for i in range(1,n+1): input.append(i) countSetBitAll(input) |
Output:
13
Time Complexity : O(log n)
Auxiliary Space: O(log n)
Another Approach:
The approach can be made more efficient using a lambda function, and the count() method in order to count the set bits in the binary form, as outlined below:
Python3
# Function to Count total set bits in all numbers# from 1 to n#Get the sum of all set bits#in the range [1, n]def countSetBitAll(n): # map count function on each number print(sum(map(lambda x: bin(x).count("1"), range(1, n + 1))))# Driver programn = 8#Function CallcountSetBitAll(n)#This code is contributed by phasing17 |
Output
13
Time Complexity : O(1 )
Auxiliary Space : O(1)
