Leetcode Problem 600. Non-negative Integers without Consecutive Ones

600. Non-negative Integers without Consecutive Ones

Leetcode Solutions

Initialize an array f of size 32, where f[i] will store the count of i-bit binary numbers without consecutive ones.
Set f[0] to 1 and f[1] to 2, as base cases for the Fibonacci sequence.
Fill the rest of the f array using the recurrence relation f[i] = f[i-1] + f[i-2] for i from 2 to 31.
Initialize sum to 0, which will store the final count of numbers without consecutive ones.
Initialize prev_bit to 0, which will track the previous bit in n.
Iterate over the bits of n from MSB to LSB using a loop.
For each bit, check if it is set (i.e., 1): a. If so, add f[i] to sum, where i is the index of the current bit from the LSB. b. If prev_bit is also 1, break the loop as we've encountered consecutive ones.
Set prev_bit to the current bit.
If the loop completes without breaking, add 1 to sum to include n itself.
Return sum as the final count.

Programming Language

Purpose:

General Question

Debug My Code

image/screenshot of info(optional)

Full Screen