TopCoder problem "CantorSet" used in SRM 284 (Division I Level Three)



Problem Statement

    The Cantor Set is an important mathematical construction devised by the 19th century mathematician Georg Cantor. It is defined as follows:

Start with the set of real numbers from 0.0 to 1.0 inclusive, which is denoted by [0.0, 1.0]. Then

  1. At step 1, remove the open middle third of [0.0, 1.0] ("open" means not including its endpoints).
  2. At step 2, remove the open middle thirds of the 2 remaining intervals.
  3. ...
  4. At step k, remove the open middle thirds of the 2^(k-1) remaining intervals.
  5. ...
The Cantor Set is the part of [0.0, 1.0] that is not removed by this process.

We want software to help determine if a given number is in the Cantor Set. Create a class CantorSet that contains a method removed that is given a String value that represents a real number in [0.0, 1.0] and returns the step at which value is removed in the above construction. If it is not removed before step 1,000,000 return 0 indicating that it is highly likely that it is in the Cantor Set.

 

Definition

    
Class:CantorSet
Method:removed
Parameters:String
Returns:int
Method signature:int removed(String value)
(be sure your method is public)
    
 

Constraints

-value will contain between 2 and 50 characters, inclusive.
-The first character in value will be '.'.
-All characters in value after the first will be digits '0'-'9'.
 

Examples

0)
    
".200"
Returns: 2
.2 is in the middle third of the lower third of [0.0, 1.0] so it is removed in step 2.
1)
    
".74928"
Returns: 14
2)
    
".975"
Returns: 0
This number is in the Cantor Set.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8081&pm=2355

Writer:

dgoodman

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Advanced Math