Consecutive Ones - Implementation

function findIntegers(n)
binary := binary representation of n as string
len := length of binary
dp := 3D array [len + 1][2][3], all -1
return solve(0, true, -1, binary)
function solve(pos, tight, prev, binary)
if pos = length of binary then return 1
t := 1 if tight else 0
p := prev + 1
if dp[pos][t][p] . = -1 then return dp[pos][t][p]
limit := binary[pos] if tight else 1
count := 0
count := count + solve(pos + 1, tight and binary[pos] = 0, 0, binary)
if prev . = 1 and limit >= 1 then
count := count + solve(pos + 1, tight and binary[pos] = 1, 1, binary)
dp[pos][t][p] := count
return count

Work in binary. Track the previous bit to avoid consecutive $1$s. The tight constraint limits choices based on $n$'s bits.

Time: $O(\log n)$. Space: $O(\log n)$.