1. Description

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.

2. Runtime Distribution

3. Submission Details

4. Example

Input: 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.

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

public int findIntegers(int num) {

	int bitCount = 0;
	int[] numInBit = new int[32];

	for (int i = num; i > 0; i >>= 1) {
		numInBit[bitCount++] = (i & 1);
	}

	int[] dp = new int[bitCount + 1];
	dp[0] = 1;
	dp[1] = 2;
	for (int i = 2; i <= bitCount; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	int result = 0;
	for (int i = bitCount - 1; i >= 0; i--) {
		if (numInBit[i] == 0) {
			continue;
		}
		result += dp[i];

		if (numInBit[i + 1] == 1) {
			return result;
		}
	}

	return result + 1;

}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

public class LeetCode0600 {

	public int findIntegers(int num) {

		int bitCount = 0;
		int[] numInBit = new int[32];

		for (int i = num; i > 0; i >>= 1) {
			numInBit[bitCount++] = (i & 1);
		}

		int[] dp = new int[bitCount + 1];
		dp[0] = 1;
		dp[1] = 2;
		for (int i = 2; i <= bitCount; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}

		int result = 0;
		for (int i = bitCount - 1; i >= 0; i--) {
			if (numInBit[i] == 0) {
				continue;
			}
			result += dp[i];

			if (numInBit[i + 1] == 1) {
				return result;
			}
		}

		return result + 1;

	}

	public static void main(String[] args) {
		System.out.println(new LeetCode0600().findIntegers(5));
	}

}

[/restab]
[/restabs]