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

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

Solution

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);
    }
}

Time Complexity

O(1)

Space Complexity

O(1)