Algorithm
Problem Name: 600. Non-negative Integers without Consecutive Ones
Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.
Example 1:
Input: n = 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.
Example 2:
Input: n = 1 Output: 2
Example 3:
Input: n = 2 Output: 3
Constraints:
1 <= n <= 109
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const findIntegers = function (num) {
const binary = num.toString(2)
const fibonacci = [1, 2]
for (let i = 2; i < binary.length; ++i) {
fibonacci.push(fibonacci[i - 2] + fibonacci[i - 1])
}
let answer = binary.indexOf('11') === -1 ? 1 : 0
for (let i = 0; i < binary.length; ++i) {
if (binary[i] === '1') {
answer += fibonacci[binary.length - 1 - i]
if (binary[i - 1] === '1') {
break
}
}
}
return answer
}
Input
n = 5
Output
5
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findIntegers(self, num):
num, sub = bin(num)[2:], 0
zero, one = [1] * len(num), [1] * len(num)
for i in range(1, len(num)):
zero[i], one[i] = zero[i - 1] + one[i - 1], zero[i - 1]
for i in range(1, len(num)):
if num[i] == num[i - 1] == "1": break
if num[i] == num[i - 1] == "0": sub += one[-1 - i]
return zero[-1] + one[-1] - sub
Input
n = 5
Output
5