TopCoder problem "PluCodeGenerator" used in SRM 255 (Division I Level Two)



Problem Statement

    

You are creating a storage management system. This system should create new PLU codes for new items. The requirements state that a PLU code must be a positive integer that does not contain three consecutive equal digits. For example, PLU codes 11211, 73399, 655 and 30 are valid PLU codes, but 11111, 73339, 555 and 3000 are invalid (they contain 111, 333, 555 and 000 respectively). For statistical purposes you want to count the number of invalid PLU codes.

You will be given an int N. You should return the number of invalid PLU codes that are less than N.

 

Definition

    
Class:PluCodeGenerator
Method:countInvalidCodes
Parameters:int
Returns:int
Method signature:int countInvalidCodes(int N)
(be sure your method is public)
    
 

Constraints

-N will be between 1 and 1000000000, inclusive.
 

Examples

0)
    
111
Returns: 0
The first invalid PLU code is 111, so there are no invalid PLU codes less than 111.
1)
    
556
Returns: 5
The invalid PLU codes less than 556 are 111, 222, 333, 444 and 555.
2)
    
1113
Returns: 13
The invalid PLU codes less than 1113 are 111, 222, 333, 444, 555, 666, 777, 888, 999, 1000, 1110, 1111 and 1112.
3)
    
7346556
Returns: 323647

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7228&pm=4473

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming