Leetcode Problem 600. Non-negative Integers without Consecutive Ones

600. Non-negative Integers without Consecutive Ones

Leetcode Solutions

Using Fibonacci Series and Bit Manipulation

  1. Initialize an array f of size 32, where f[i] will store the count of i-bit binary numbers without consecutive ones.
  2. Set f[0] to 1 and f[1] to 2, as base cases for the Fibonacci sequence.
  3. 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.
  4. Initialize sum to 0, which will store the final count of numbers without consecutive ones.
  5. Initialize prev_bit to 0, which will track the previous bit in n.
  6. Iterate over the bits of n from MSB to LSB using a loop.
  7. 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.
  8. Set prev_bit to the current bit.
  9. If the loop completes without breaking, add 1 to sum to include n itself.
  10. Return sum as the final count.
UML Thumbnail

Brute Force Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...