FastPrepTotal Set Bits from 1 to N
Problems/Total Set Bits from 1 to N

Total Set Bits from 1 to N

PeopleStrong logoPeopleStrong● MediumFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a PeopleStrong online assessment. The task counts the set bits from 1 through N, modulo 10^9+7. We chose the function interface and a practical limit for N. Our version is about 95% the same as the reported question.

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) → int

Examples

Example 1

n = 3return = 4

The binary forms 1, 10 and 11 contain 1, 1 and 2 set bits, totaling 4.

Example 2

n = 7return = 12

Across 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

Interview reports that mention this question

  • PeopleStrong SDE OA and Interview Questions: 12 Experiences
All PeopleStrong interview questionsSee PeopleStrong hiring insights
Saved
class Solution {
    public int totalSetBits(long n) {
        // Write your solution here.
    }
}
Checking account…