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.



Method signature:int removed(String value)
(be sure your method is public)


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


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

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy

Problem categories:

Advanced Math