LeetCode 600 · Non-negative Integers without Consecutive Ones — Java SolutionIntuitionCount integers in“[0, num]” whose binary representation contains no two adjacent1s (“11” is forbidden).A clean digit-DP approach: scan“num” bit-by-bit from MSB → LSB. Whenever the current bit of“num” is“1”, we can force this bit to“0” and freely fill the remaining lower“i” bits with any valid pattern — then continue matching“num” with this bit kept as“1”.The count of length-“k” binary strings (leading zeros allowed) without consecutive ones follows the Fibonacci recurrence.Precomputation: Fibonacci ArrayLet“fib[k]” number of valid bit-strings of exactly“k” remaining positions.k valid strings fib[k]0“”“” 11“0”,“1” 22“00”,“01”,“10” 3Recurrence:“fib[k] fib[k-1] fib[k-2]”Java Implementation (Digit DP, O(log num) time)class Solution {public int findIntegers(int num) {// fib[k]: # valid binary strings of length k (leading zeros OK)// fib[0] 1, fib[1] 2int[] fib new int[32];fib[0] 1;fib[1] 2;for (int i 2; i 32; i) {fib[i] fib[i - 1] fib[i - 2];}int ans 0; int prevBit 0; // tracks whether the previous scanned bit was 1 // scan from bit 30 down to 0 (bit 31 is the sign bit) for (int i 30; i 0; i--) { int cur (num i) 1; if (cur 1) { // choose this bit 0 instead, lower i bits are free → add fib[i] ans fib[i]; // if previous bit was also 1, num itself is invalid; stop early if (prevBit 1) { return ans; } prevBit 1; } else { prevBit 0; } } // num itself has no consecutive 1s → count it too return ans 1; }}Walkthrough (“num 5” → binary“101”)i bit action ans2“1” add“fib[2]3” (strings“0xx”: 0,1,2) 31“0” nothing,“prevBit0” 30“1” add“fib[0]1” (“100” 4) 4done —“101” is valid,“1” 5Valid set:“{0, 1, 2, 4, 5}” ✅ComplexityTime“O(log num)” — single pass over 31 bitsSpace“O(1)” — fixed-size“fib[32]” arrayCommon Pitfalls❌ Using“Integer.bitCount” / brute force → TLE for“num” up to“2·10⁹”❌ Off-by-one on the“fib” index —“fib[i]” corresponds to“i” remaining lower bits, not“i1”❌ Forgetting the final“1” when“num” itself is a valid number❌ Not returning early when“prevBit 1” — once“num” contains“11”, the tight path diesOne-liner Comparison with Related ProblemsProblem TechniqueLC 600 (this) Digit DP FibonacciLC 233 · Number of Digit One Digit DPLC 790 · Domino and Tromino Same Fibonacci recurrence“dp[i]dp[i-1]dp[i-2]”Want me to also provide the memoized recursive digit-DP version, or a Kotlin / Python translation for side-by-side review?