CantorSet

SRM 284 · 2006-01-21 · by dgoodman

SRM 284 · 2006-01-21 · by dgoodman · Advanced Math

Show categories

Class Name: CantorSet

Return Type: int

Method Name: removed

Arg Types: (string)

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

At step 1, remove the open middle third of [0.0, 1.0] ("open" means not including its endpoints).
At step 2, remove the open middle thirds of the 2 remaining intervals.
...
At step k, remove the open middle thirds of the 2^(k-1) remaining intervals.
...

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.

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

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

".00000000000000000000000000000000000000000400"
Returns: 87

".74928"
Returns: 14

".975"
Returns: 0

This number is in the Cantor Set.

".9749999999999999999999999999999999999999999999999"
Returns: 106

Submissions are judged against all 68 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CantorSet with a public method int removed(string value) · 68 test cases · 2 s / 256 MB per case