The problem
Write every whole number from 0 to n in binary. Return how many 1 bits there are in all of them together.
ones_upto(5) # 7: 0, 1, 10, 11, 100, 101
ones_upto(7) # 12
ones_upto(0) # 0
Limits
nis from 0 to 10¹⁰⁰ (a 1 followed by 100 zeros). Counting the bits of every number is far too slow above a few million.
Builds on BITS-4 Counting bits.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
12 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Zero | Not run | |
| 3 | One | Not run | |
| 4 | Up to 7 | Not run | |
| 5 | Up to 8 | Not run | |
| 6 | Every n below 40 | Not run | |
| 7 | A thousand | Not run | |
| 8 | A million | Not run | |
| 9 | A billion | Not run | |
| 10 | All 60-bit numbers | Not run | |
| 11 | 10¹⁸ | Not run | |
| 12 | 10¹⁰⁰ | Not run |