top of page

### Looking to master object-oriented and system design for tech interviews or career growth?

• Improve your system design and machine coding skills.

• Study with our helpful resources.

**We're in beta mode and would love to hear your feedback.

Search

# Count Total Set Bits - InterviewBit Solution

### Problem Description:

Given a positive integer A, the task is to count the total number of set bits in the binary representation of all the numbers from 1 to A Return the count modulo 109 + 7.

Problem Constraints

`1 <= A <= 109`

Input Format

The first and only argument is an integer A.

Output Format

Return an integer denoting the ( Total number of set bits in the binary representation of all the numbers from 1 to A )modulo 109 + 7.

Example Input

```Input 1:
A = 3
Input 2:
A = 1 ```

Example Output

```Output 1:
4
Output 2:
1 ```

### Example Explanation

Explanation 1:

``` DECIMAL    BINARY  SET BIT COUNT
1          01        1
2          10        1
3          11        2
1 + 1 + 2 = 4
Answer = 4 % 1000000007 = 4
```

Explanation 2:

``` A = 1
DECIMAL    BINARY  SET BIT COUNT
1          01        1
Answer = 1 % 1000000007 = 1```

### Solution in C++:

If you have any questions or queries, feel free to drop a comment in the comments section below.