Total Set Bits from 1 to N
Updated
Problem statement
Given a positive integer n, count all set bits in the binary representations of every integer from 1 through n, inclusive. A set bit is a binary digit equal to 1.
Return the total modulo 1,000,000,007. For this exercise, assume n is at most one billion.
Function
totalSetBits(n: long) → intExamples
Example 1
n = 3return = 4The binary forms 1, 10 and 11 contain 1, 1 and 2 set bits, totaling 4.
Example 2
n = 7return = 12Across the values from 0 to 7, each of the three bit positions is set four times. Zero adds no set bits, so the answer for 1 to 7 is 12.
Constraints
- For this exercise, assume
1 <= n <= 10^9. - Return the count modulo
10^9 + 7. - Use 64-bit intermediate arithmetic.
More PeopleStrong interview questions
- Reverse Linked-List Nodes in Groups of KOA · PHONE SCREEN · Seen Mar 2026
- Unique Paths Through a GridOA · Seen Mar 2026
- Aggressive CowsOA · Seen Oct 2021
- Shortest Path in an Unweighted GraphOA · Seen Oct 2021
- Swap Two Array ElementsOA · Seen Sep 2021
- Minimum Travel Time with Flashing Traffic LightsOA · Seen Aug 2021
- Permutation in a StringOA · Seen Aug 2021
- Rat in a Maze: All Simple PathsOA · Seen Aug 2021
- Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
- Four SumONSITE INTERVIEW · Seen Mar 2026
Similar questions at other companies
- Knights, Knaves and Their StatementsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions
- Repeated Mirror XORMathWorks · OAMathWorks interview questions
- Minimum Power-of-Two Removal OperationsIBM · OAIBM interview questions
- Minimum Power-of-Two Removal OperationsVisa · OAVisa interview questions
- Minimum Operations To Reduce To ZeroUber · OAUber interview questions
- City Infection NumberArcesium · OAArcesium interview questions
- Minimum Power-of-Two AdjustmentsNVIDIA · OANVIDIA interview questions
- Minimum Testers to Find the Poisoned BottleWalleye Capital · OA
- Find the Missing Number from 1 to nGEP · OA