TopCoder problem "CoolNumbers" used in TCHS SRM 26 (Division I Level Three)



Problem Statement

    

A cool number is a non-negative integer that contains at least three consecutive ones or three consecutive zeroes in its binary representation (without leading zeroes). For example, 8 (1000 binary) and 15 (1111 binary) are cool numbers, but 27 (11011 binary) is not.

Return the number of cool numbers between lowerBound and upperBound, inclusive.

 

Definition

    
Class:CoolNumbers
Method:count
Parameters:int, int
Returns:int
Method signature:int count(int lowerBound, int upperBound)
(be sure your method is public)
    
 

Constraints

-upperBound will be between 0 and 2147483647, inclusive.
-lowerBound will be between 0 and upperBound, inclusive.
 

Examples

0)
    
0
16
Returns: 5
Following numbers between 0 and 16, inclusive are cool:

7 (111 binary)

8 (1000 binary)

14 (1110 binary)

15 (1111 binary)

16 (10000 binary)
1)
    
17
100
Returns: 49
2)
    
2000000000
2100000000
Returns: 100000001
3)
    
2
6
Returns: 0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6744

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10650&pm=6744

Writer:

gevak

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming