LeetCode 600 Non-negative Integers without Consecutive Ones - Problem Statement

Given a positive integer $n$, return the number of non-negative integers $\leq 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.