bits of a number n (with no leading zeros) and an integer steps.
A step replaces a positive integer x with the number of ones in its binary representation. For example, 13 = 1101₂ becomes 3, and 3 = 11₂ becomes 2.
A number x **collapses** if it turns into 1 within at most steps steps (the number 1 itself collapses in zero steps).
Count the positive integers less than n that collapse. The answer can be huge, so return it modulo 10⁹ + 7.
Note that bits can be up to 800 characters long, so going through all the numbers is out of the question.bits="110", steps=1 → 3
The bound is 6. Only numbers with a single set bit reach 1 in one step: 1, 2 and 4.
bits="1010", steps=2 → 8
The bound is 10. Numbers with one set bit (1, 2, 4, 8) qualify, and so do those with two (3, 5, 6, 9): they turn into 2 and then into 1. The number 7 goes 3 → 2 → 1, which takes three steps.
bits="10", steps=5 → 1
The bound is 2; the only number below it is 1, which is already 1.
bits consists of 0 and 1 and starts with 1bits="110", steps=1
3
Run checks the first 3 tests in your browser. Submit checks all 40 tests on the server, hidden ones included.