600. Non-negative Integers without Consecutive Ones

Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

Example 1:

Note: 1 <= n <= 109


Leave a Reply

Your email address will not be published. Required fields are marked *