Non-negative Integers without Consecutive Ones

• Initialize a counter count to 0.
• Iterate through each integer i from 0 to n.
• For each integer i, check if its binary representation contains consecutive ones.
• A simple way to check this is using bit manipulation. If (i & (i >> 1)) is non-zero, it means there was at least one position where a bit and its adjacent bit to the right were both 1.
• If i does not have consecutive ones, increment the count.
• After the loop finishes, return count.

This approach involves a simple loop from 0 to n. Inside the loop, for each number i, we perform a check. The check for consecutive ones can be done by converting the number to a binary string and searching for the substring "11", but a more efficient bitwise trick exists. By taking the number i and bitwise ANDing it with itself right-shifted by one (i >> 1), we can detect consecutive ones. If the result of i & (i >> 1) is not zero, it implies that there was some bit position k where both the k-th bit and (k-1)-th bit were 1, indicating consecutive ones. While the check for each number is very fast (O(1)), the overall algorithm's performance is limited by the loop that runs n+1 times.

1class Solution {2    public int findIntegers(int n) {3        int count = 0;4        for (int i = 0; i <= n; i++) {5            // Check for consecutive ones using a bitwise trick.6            // If (i & (i >> 1)) is non-zero, it means there was a '11' pattern.7            if ((i & (i >> 1)) == 0) {8                count++;9            }10        }11        return count;12    }13}

• Convert the input integer n into its binary string representation, let's call it s.
• Create a recursive function, say solve(index, tight, prevIsOne), which counts the number of valid ways to complete a number from a given state.
• The state is defined by:
  • index: The current bit position we are filling (from left to right).
  • tight: A boolean (or integer 0/1) flag. It's true if we are restricted to the digits of n's binary string s (i.e., we've matched the prefix of s so far). If false, we can use any digit (0 or 1).
  • prevIsOne: A boolean (or integer 0/1) flag, true if the previously placed bit was a 1.
• Use a memoization table (e.g., a 3D array memo[index][tight][prevIsOne]) to store the results of subproblems.
• The base case for the recursion is when index reaches the end of the string s, meaning we have successfully formed one valid number. In this case, return 1.
• In the recursive step, iterate through the possible digits d for the current index. The upper bound for d is s[index] if tight is true, otherwise it's 1.
• If prevIsOne is true, we cannot place a 1. So, we skip d=1.
• For each valid d, make a recursive call solve(index + 1, newTight, newPrevIsOne) and add the result to the total count. The newTight flag will be true only if the original tight was true and we chose the maximum possible digit d.
• The initial call to the function would be solve(0, true, false).

The core idea is to count the valid numbers by constructing them from the most significant bit to the least significant bit. We define a recursive function with memoization to count the number of ways to fill the remaining bits of a number, given a certain prefix.

The state of our DP needs to capture all the necessary information to make decisions for the subsequent bits. This includes:

1. index: The current bit position we are considering.
2. tight: A constraint flag. If the prefix we've built so far is identical to the prefix of n, then for the current index, we can only choose a bit up to n's bit at that index. If our prefix is already smaller, we are no longer 'tightly' constrained and can choose any bit (0 or 1).
3. prevIsOne: A flag to remember if the immediate preceding bit was a 1, to enforce the no-consecutive-ones rule.

By memoizing the results for each state (index, tight, prevIsOne), we avoid recomputing the same subproblems, leading to a very efficient solution.

1import java.util.Arrays;2 3class Solution {4    int[][][] memo;5    String s;6 7    public int findIntegers(int n) {8        s = Integer.toBinaryString(n);9        memo = new int[s.length()][2][2];10        for (int[][] arr2D : memo) {11            for (int[] arr1D : arr2D) {12                Arrays.fill(arr1D, -1);13            }14        }15        // solve(index, tight_constraint, previous_bit_is_one)16        return solve(0, 1, 0);17    }18 19    private int solve(int index, int tight, int prevIsOne) {20        if (index == s.length()) {21            return 1; // Found a valid number22        }23        if (memo[index][tight][prevIsOne] != -1) {24            return memo[index][tight][prevIsOne];25        }26 27        int ans = 0;28        int upperBound = (tight == 1) ? (s.charAt(index) - '0') : 1;29 30        for (int digit = 0; digit <= upperBound; digit++) {31            if (prevIsOne == 1 && digit == 1) {32                continue; // Avoid consecutive ones33            }34            35            // The new tight constraint is true only if the old one was true36            // AND we are placing the maximum possible digit.37            int newTight = (tight == 1 && digit == upperBound) ? 1 : 0;38            ans += solve(index + 1, newTight, digit);39        }40 41        return memo[index][tight][prevIsOne] = ans;42    }43}

• First, observe that the number of binary strings of length k without consecutive ones follows the Fibonacci sequence. Let f[k] be this count. We have f[0] = 1 (empty string), f[1] = 2 ('0', '1'), and f[k] = f[k-1] + f[k-2]. This is because a valid string of length k can be formed by appending '0' to any valid string of length k-1, or by appending '1' to a valid string of length k-1 that ends in '0' (which is equivalent to any valid string of length k-2 followed by '0').
• Precompute these Fibonacci-like numbers up to the number of bits in n.
• Convert n to its binary string s of length L.
• Initialize count = 0 and a flag prevBit = 0.
• Iterate through the bits of s from left to right (from index i = 0 to L-1).
  • If the current bit s[i] is '1':
    • We can form valid numbers by placing a '0' at this position. The number of ways to fill the remaining L-1-i bits is f[L-1-i]. Add this to count.
    • If the previous bit (s[i-1]) was also '1', it means n itself (and any number with this prefix) has consecutive ones. We have already counted all valid numbers strictly smaller than n, so we can stop and return the current count.
  • Update prevBit to the current bit's value.
• If the loop completes, it means n itself does not have consecutive ones. The count currently holds the number of valid integers strictly less than n. So, we add 1 to include n itself.
• Return the final count.

The key observation is that the count of non-negative integers without consecutive ones for a given number of bits relates to the Fibonacci sequence. Let f[i] be the number of valid binary strings of length i.

• f[0] = 1 (the empty string)
• f[1] = 2 ("0", "1")
• f[2] = 3 ("00", "01", "10")
• f[3] = 5 ("000", "001", "010", "100", "101") This sequence is f[i] = f[i-1] + f[i-2], which is the Fibonacci sequence (shifted).

We can leverage this to count the valid numbers up to n. We scan the binary representation of n from the most significant bit. At each bit i, if n has a '1', we can calculate how many valid numbers could have been formed by placing a '0' at that bit instead. The number of ways to complete the number from there is simply f[k] where k is the number of remaining bits. We add this to our total. If we encounter consecutive '1's in n's binary string, we stop early, as n and any number with that prefix would be invalid. Finally, if n itself is a valid number, we add it to the count.

1class Solution {2    public int findIntegers(int n) {3        String s = Integer.toBinaryString(n);4        int len = s.length();5        6        // f[i] = number of valid binary strings of length i7        int[] f = new int[len + 1];8        f[0] = 1;9        f[1] = 2;10        for (int i = 2; i <= len; i++) {11            f[i] = f[i - 1] + f[i - 2];12        }13 14        int count = 0;15        int prevBit = 0;16        for (int i = 0; i < len; i++) {17            int bit = s.charAt(i) - '0';18            if (bit == 1) {19                // If we place a '0' at this position, any valid combination20                // for the remaining bits is allowed. The number of remaining21                // bits is (len - 1 - i).22                count += f[len - 1 - i];23                if (prevBit == 1) {24                    // Found '11' in n's binary representation.25                    // All numbers with this prefix are invalid, including n.26                    // The count we have is for numbers < n. So, we can return.27                    return count;28                }29            }30            prevBit = bit;31        }32 33        // The loop counted all valid numbers < n.34        // Since the loop finished without returning, n itself is valid.35        return count + 1;36    }37}