Statistics

Problem Statement for "CantorSet"

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

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

  2. ".00000000000000000000000000000000000000000400"

    Returns: 87

  3. ".74928"

    Returns: 14

  4. ".975"

    Returns: 0

    This number is in the Cantor Set.

  5. ".9749999999999999999999999999999999999999999999999"

    Returns: 106

  6. ".0000000000000000000000000000000000000000000122941"

    Returns: 127

  7. ".0000000000000000000000000000000000000000000009548"

    Returns: 117

  8. ".0"

    Returns: 0

  9. ".9"

    Returns: 0

  10. ".9000000000000000000000000000000000000000000009453"

    Returns: 119

  11. ".8"

    Returns: 2

  12. ".337"

    Returns: 1

  13. ".6"

    Returns: 1

  14. ".9999999999999999999999999999999999999999999999999"

    Returns: 103

  15. ".1112345"

    Returns: 2

  16. ".12345"

    Returns: 2

  17. ".7001099"

    Returns: 7

  18. ".1"

    Returns: 0

  19. ".1000000000000000000000000000000000000000000000000"

    Returns: 0

  20. ".7000000000000000000000000000000000000000000000000"

    Returns: 0

  21. ".0000000000000000000000000000000000000000000000001"

    Returns: 103

  22. ".0000000000000000000000000000000000000000000000002"

    Returns: 105

  23. ".0000000000000000000000000000000000000000000000003"

    Returns: 102

  24. ".0000000000000000000000000000000000000000000000004"

    Returns: 102

  25. ".0000000000000000000000000000000000000000000000005"

    Returns: 106

  26. ".0000000000000000000000000000000000000000000000006"

    Returns: 104

  27. ".0000000000000000000000000000000000000000000000007"

    Returns: 101

  28. ".0000000000000000000000000000000000000000000000008"

    Returns: 101

  29. ".0000000000000000000000000000000000000000000000009"

    Returns: 101

  30. ".0000000000000000000000000000000000000000000000000"

    Returns: 0

  31. ".075"

    Returns: 0

  32. ".025"

    Returns: 0

  33. ".0750000000000000000000000000"

    Returns: 0

  34. ".0250"

    Returns: 0

  35. ".3250"

    Returns: 0

  36. ".02500"

    Returns: 0

  37. ".10000"

    Returns: 0

  38. ".22500"

    Returns: 0

  39. ".225000"

    Returns: 0

  40. ".925000"

    Returns: 0

  41. ".0118605"

    Returns: 7

  42. ".0118605"

    Returns: 7

  43. ".330269761236"

    Returns: 19

  44. ".4249717191642938874771436183"

    Returns: 1

  45. ".0278750606311674235588545332470"

    Returns: 10

  46. ".45759582818588442027654025321305275096575569"

    Returns: 1

  47. ".25829584021966"

    Returns: 21

  48. ".2482838798054623461551841268010179406247910065"

    Returns: 20

  49. ".004797385650214389"

    Returns: 5

  50. ".3333333333333333333333333333333333333333333333333"

    Returns: 104

  51. ".6666666666666666666666666666666666666666666666668"

    Returns: 103

  52. ".33333333333333333333333333333333333333333334"

    Returns: 1

  53. ".3333333333333333333333333333333333333333235325322"

    Returns: 86

  54. ".9999999999999984"

    Returns: 38

  55. ".9750000000000000000000000000000000000000000000001"

    Returns: 100

  56. ".666666666666666666666666666666666666666666666667"

    Returns: 102

  57. ".123460963214612348612934912348602164312630416043"

    Returns: 2

  58. ".3250000000000000000000000000000000000000000000000"

    Returns: 0

  59. ".9999999999999999999999999999999999999999999999999"

    Returns: 103

  60. ".3333333333333333333333333333333333333333334"

    Returns: 1

  61. ".6750000000000000000000000000000000000000000000001"

    Returns: 103

  62. ".333333333333333333333333333333333333333333"

    Returns: 94

  63. ".33333333333333333333333333333333333"

    Returns: 85

  64. ".3333333333333333333333333333333333333"

    Returns: 79

  65. ".975934759870240814895345"

    Returns: 4

  66. ".6750000000000000000000000000000000000000000000000"

    Returns: 0

  67. ".333333333333333333333333333333333333333333333332"

    Returns: 104

  68. ".9999999999999999999999999999999999999999"

    Returns: 84

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: