# Non-negative Integers without Consecutive Ones

This page explains Java solution to problem `Non-negative Integers without Consecutive Ones` using `Bit Manipulation`.

## Problem Statement

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))`.

Example 1:

Input: 5
Output: 5
Explanation:
Here are the non-negative integers

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
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)