This page explains Java solution to problem `Non-negative Integers without Consecutive Ones`

using `Bit Manipulation`

.

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.

Follow up: The overall run time complexity should be `O(log (m+n))`

.

Input: 5Output: 5Explanation:

Here are the non-negative integers

```
package com.vc.hard;
class NonNegativeIntegersWithoutConsecutiveOnes {
public int findIntegers(int num) {
char[] str = Integer.toBinaryString(num).toCharArray();
int len = str.length;
int endingInZero = 0;
int endingInOne = 0;
boolean isPrefixValid = true;
for (int i = 0; i < len; i++) {
//Fibonacci Series
int total = endingInZero + endingInOne;
// You can append one to only those seq where last digit was zero
endingInOne = endingInZero;
// You can append zero to any seq
endingInZero = total;
if (isPrefixValid) {
if (str[i] == '1') {
endingInZero++;
if (i > 0 && str[i - 1] == '1') {
isPrefixValid = false;
}
}
}
}
return endingInZero + endingInOne + (isPrefixValid ? 1 : 0);
}
}
```

O(1)

O(1)