Given a positive integer n, return the number of non-negative integers ≤n whose binary representation does not contain consecutive ones. For n=5 (binary 101): valid numbers are 0,1,2,4,5 (binary 0,1,10,100,101). Invalid: 3 (binary 11).
Answer: 5. This is digit DP on binary representation. Instead of base 10, you work in base 2. Before reading the solution, try to identify the base case and recursive relationship yourself.