The problem
Count the whole numbers x with a ≤ x ≤ b in which no two neighbouring digits are equal, written in the usual way with no zeros in front. So 1213 counts, 1223 does not, and 100 does not (two zeros). The number 0 counts: it has one digit.
count_no_repeat(0, 100) # 91
count_no_repeat(10, 20) # 10: every number but 11
Limits
- 0 ≤ a ≤ b ≤ 10¹⁸, so counting the numbers one by one is impossible.
Builds on ADDP-5 Digit DP.
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.
13 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | One to nine | Not run | |
| 2 | Zero | Not run | |
| 3 | Up to 100 | Not run | |
| 4 | From 10 to 20 | Not run | |
| 5 | A single bad number | Not run | |
| 6 | A single good number | Not run | |
| 7 | Leading zeros are not digits | Not run | |
| 8 | Counting from a | Not run | |
| 9 | Up to 10¹⁸ | Not run | |
| 10 | A big range | Not run | |
| 11 | A tight path that breaks early | Not run | |
| 12 | From ten nines to 10¹¹ | Not run | |
| 13 | Many ranges | Not run |