# ---
# title: 600. Non-negative Integers without Consecutive Ones
# id: problem600
# author: Tian Jun
# date: 2020-10-31
# difficulty: Hard
# categories: Dynamic Programming
# link: <https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/description/>
# hidden: true
# ---
# 
# 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:**  
# 
#     
#     
#     Input: 5
#     Output: 5
#     Explanation: 
#     Here are the non-negative integers <= 5 with their corresponding binary representations:
#     0 : 0
#     1 : 1
#     2 : 10
#     3 : 11
#     4 : 100
#     5 : 101
#     Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 
#     
# 
# **Note:** 1 <= n <= 109
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
