@@ -0,0 +1,1101 @@
+# Time:  O(1)%0A# Space: O(1)%0A%0A# Given a positive integer n, find the number of non-negative integers less than%0A# or equal to n, whose binary representations do NOT contain consecutive ones.%0A#%0A# Example 1:%0A# Input: 5%0A# Output: 5%0A# Explanation: %0A# Here are the non-negative integers %3C= 5 with their corresponding binary representations:%0A# 0 : 0%0A# 1 : 1%0A# 2 : 10%0A# 3 : 11%0A# 4 : 100%0A# 5 : 101%0A# Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. %0A# Note: 1 %3C= n %3C= 10%5E9%0A%0Aclass Solution(object):%0A    def findIntegers(self, num):%0A        %22%22%22%0A        :type num: int%0A        :rtype: int%0A        %22%22%22%0A        dp = %5B0%5D * 32%0A        dp%5B0%5D, dp%5B1%5D = 1, 2%0A        for i in xrange(2, len(dp)):%0A            dp%5Bi%5D = dp%5Bi-1%5D + dp%5Bi-2%5D%0A        result, prev_bit = 0, 0%0A        for i in reversed(xrange(31)):%0A            if (num & (1 %3C%3C i)) != 0:%0A                result += dp%5Bi%5D%0A                if prev_bit == 1:%0A                    result -= 1%0A                    break%0A                prev_bit = 1%0A            else:%0A                prev_bit = 0%0A        return result + 1%0A

Create non-negative-integers-without-consecutive-ones.py