Statistics

Problem Statement for "DoubleOrOne"

Problem Statement

You are given two ints: a and b. You are now going to perform a sequence of zero or more steps. In each step you will double one of the integers and increment the other. Your goal is to reach a state in which both integers have the same value.

More precisely, in each step you will perform one of the following two moves:

  • Move '0': add 1 to a, multiply b by 2
  • Move '1': multiply a by 2, add 1 to b

Any sequence of steps can now be written as a string of zeros and ones. It is guaranteed that for each pair a, b that satifies the constraints (given below) it is possible to reach the goal in at most 2500 steps. Find any such sequence of steps and return a String containing its description.

Note that your solution does not have to minimize the number of steps. Any valid solution that consists of at most 2500 steps will be accepted.

Definition

Class:
DoubleOrOne
Method:
findSequence
Parameters:
int, int
Returns:
String
Method signature:
String findSequence(int a, int b)
(be sure your method is public)

Notes

  • The fact that a and b are given as ints does not imply any upper bound on their values. For example, if you start with a=1 and perform move '1' exactly 1000 times, you will have a=2^1000.

Constraints

  • a,b will be between 0 and 100, inclusive.

Examples

  1. 1

    1

    Returns: ""

    Nothing needs to be done here.

  2. 1

    2

    Returns: "11"

    One way to make a,b equal is to apply move '1' twice. In this case, we get the following sequence: (1,2) -> (2,3) -> (4,4).

  3. 2

    1

    Returns: "1110100"

    This example is the same as Example 1, only with a and b swapped. Here we intentionally show a different correct sequence of steps. Note that the answer "00" would also be accepted.

  4. 10

    24

    Returns: "001101011"

    (10, 24) -> (11, 48) -> (12, 96) -> (24, 97) -> (48, 98) -> (49, 196) -> (98, 197) -> (99, 394) -> (198, 395) -> (396, 396)

  5. 0

    64

    Returns: "10111101111"

  6. 99

    98

    Returns: "11000011001011"

  7. 100

    0

    Returns: "111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111110111111111111111100000010000"

  8. 0

    100

    Returns: "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000001000000000000000011111101111"

  9. 1

    98

    Returns: "11001101101111"

  10. 42

    49

    Returns: "000000011110111111110010000011110100"

  11. 37

    99

    Returns: "00000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111110111111111111111100000010000"

  12. 69

    70

    Returns: "100001101011"

  13. 92

    58

    Returns: "1111111111111111111111111111111111000000000000000000000000000001000000"

  14. 79

    45

    Returns: "1111111111111111111111111111111111000000000000000000000000000001000000"

  15. 38

    10

    Returns: "00"

  16. 91

    84

    Returns: "111111100001000000001101111100001011"

  17. 67

    77

    Returns: "0000000000111111101111001011"

  18. 87

    9

    Returns: "1111111111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000000000001000000011111111111111111111111000000000000000000010000011111111111000000001000011110010000011110100"

  19. 100

    96

    Returns: "11110010000011110100"

  20. 52

    89

    Returns: "00000000000000000000000000000000000001111111111111111111111111111111101111110000001111011100011011001011"

  21. 99

    51

    Returns: "0010001101011"

  22. 33

    64

    Returns: "11100001011"

  23. 67

    76

    Returns: "00000000011111101111"

  24. 36

    92

    Returns: "00000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111110111111111111111111111111111100000000000000000100000111111100001000000001101111100001011"

  25. 69

    39

    Returns: "11111111111111111111111111111100000000000000000000000001000000000000001111101111110100"

  26. 77

    97

    Returns: "0000000000000000000011111111111111110111110000011101110011110100"

  27. 41

    70

    Returns: "0000000000000000000000000000011111111111111111111111101111111111111111000000010000110100"

  28. 26

    59

    Returns: "00000000000000000000000000000000011111111111111111111111111110111111110100"

  29. 59

    88

    Returns: "0000000000000000000000000000011111111111111111111111101111111111111111000000010000110100"

  30. 73

    71

    Returns: "110100"

  31. 55

    39

    Returns: "111111111111111100000000000010000000011011001011"

  32. 25

    34

    Returns: "00000000011111101111"

  33. 45

    17

    Returns: "1111111111111111111111111111000000000000000000000001000000000000000000111111111011110000001111011100011011001011"

  34. 48

    40

    Returns: "111111110000010000001011"

  35. 55

    19

    Returns: "1111111111111111111111111111111111110000000000000000000000000000000100000011110010000011110100"

  36. 99

    18

    Returns: "111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000100000001111111111111111111111111111100000000000000000000000010000000000000000111111101111001011"

  37. 48

    54

    Returns: "0000001111011100011011001011"

  38. 85

    59

    Returns: "111111111111111111111111110000000000000000000001000000000000000000000011111111111101111111100100110100"

  39. 6

    65

    Returns: "0011101001111"

  40. 26

    72

    Returns: "0000000000000000000000000000000000000000000000111111111111111111111111111111111111111110111111000000000000000000000000111111111111111111110111110000000000000111111111101111000000001111101111110100"

  41. 91

    19

    Returns: "1111111111111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000000000001000000011111111111000000001000011110010000011110100"

  42. 38

    19

    Returns: "1000011001011"

  43. 30

    62

    Returns: "10001101011"

  44. 71

    27

    Returns: "1111111111111111111111111111111111111111111100000000000000000000000000000000000000010000001111111111111111111100000000000000001000001111100010001100001011"

  45. 63

    97

    Returns: "0000000000000000000000000000000000111111111111111111111111111110111111"

  46. 97

    78

    Returns: "111111111111111111100000000000000010000011100100110100"

  47. 45

    3

    Returns: "000100001011"

  48. 8

    35

    Returns: "10011011001011"

  49. 4

    12

    Returns: "11110100"

  50. 42

    22

    Returns: "0100001101011"

  51. 84

    24

    Returns: "111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000100000000000000000000111111111101111000000001111101111110100"

  52. 70

    75

    Returns: "00001001101111"

  53. 61

    8

    Returns: "000"

  54. 72

    13

    Returns: "111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000010000000000000000000000111111111110111111111100010001100001011"

  55. 95

    31

    Returns: "11111111111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000000000100000000000011101110011110100"

  56. 92

    87

    Returns: "11110110010000"

  57. 58

    0

    Returns: "11111111111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000000100000000000000000000000011111111111110111111100001011"

  58. 7

    96

    Returns: "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111100000000000000000000000000000000000000000000011111111111111111111111111111111111111110111111000000000000000000000011111111111111111101111100000000011111101111"

  59. 52

    98

    Returns: "0000000000000000000000000000000000000000000000111111111111111111111111111111111111111110111111000000000000000000000000111111111111111111110111110000000000000111111111101111000000001111101111110100"

  60. 24

    76

    Returns: "00000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111011111111111111111111111111111111111100000000000000000000000010000000000000000111111101111001011"

  61. 7

    99

    Returns: "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111011111110000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111110111111111111111111111111111111111111110000000000000000000000000010000000000001111011100011011001011"

  62. 14

    87

    Returns: "00000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111011111110000000000000111111111101111000000001111101111110100"

  63. 100

    40

    Returns: "111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000100000000000000000000111111111101111000000001111101111110100"

  64. 20

    65

    Returns: "00000000000000000000000000000000000000000000011111111111111111111111111111111111111110111111000000000000000000000011111111111111111101111100000000011111101111"

  65. 74

    47

    Returns: "11111111111111111111111111100000000000000000000001000000000000000000001111111111011111111111100001000000001101111100001011"

  66. 13

    93

    Returns: "00000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111110111111100000000000000000000000000011111111111111111111110111111111111111111110000000000100000000000011110111111110010000011110100"

  67. 70

    99

    Returns: "0000000000000000000000000000011111111111111111111111101111111111111111000000010000110100"

  68. 74

    100

    Returns: "000000000000000000000000001111111111111111111110111111111111111111111100000000000010000000011011001011"

  69. 85

    100

    Returns: "000000000000000111111111110111111111100010001100001011"

  70. 67

    25

    Returns: "11111101111100000001101000000"

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: