Statistics

Problem Statement for "RepeatedPatterns"

Problem Statement

Given are two Strings P1 and P2. Each of these strings contains a pattern of zeros and ones.

The string S(n) is formed by concatenating 1,000,000 copies of P1 followed by n copies of P2.

The infinite string S is formed by concatenating the strings S(1), S(2), S(3), ... in this order.

The string T consists of the first 10^16 characters of the string S.

We are interested in substrings of T that are zeroCount characters long and contain only zeros. Write a method that finds the first occurrence of such a substring in T, and returns the zero-based index of its first character. In case T contains no such substring return -1.

Definition

Class:
RepeatedPatterns
Method:
findZeroSegment
Parameters:
String, String, String
Returns:
long
Method signature:
long findZeroSegment(String P1, String P2, String zeroCount)
(be sure your method is public)

Notes

  • The number zeroCount may be large, and therefore it is specified as a String.

Constraints

  • P1 will contain between 1 and 50 characters, inclusive.
  • P2 will contain between 1 and 50 characters, inclusive.
  • P1 and P2 will contain only zeroes ('0') and ones ('1').
  • zeroCount will contain between 1 and 17 characters, inclusive.
  • zeroCount will contain only digits ('0'-'9').
  • zeroCount will represent a positive integer between 1 and 10^16, inclusive.
  • zeroCount will not contain leading zeros.

Examples

  1. "111010100001010"

    "010000001000"

    "3"

    Returns: 7

    The first occurrence of three consecutive zeroes is right in the first copy of P1.

  2. "1101010010"

    "0001000"

    "3"

    Returns: 9999999

    This time the first substring "000" starts with the last character of the 1,000,000th copy of P1.

  3. "1101010010"

    "0001000"

    "5"

    Returns: 20000011

    We have the same string T as in Example 1, only we look for the substring "00000". The first occurrence is between the second and the third copy of P2.

  4. "10101010"

    "101010101010"

    "9876543219876"

    Returns: -1

    Nowhere in the infinite string S can we find two consecutive zeroes. Clearly, in the string T there is no substring with 9876543219876 consecutive zeroes.

  5. "11111111111111111111111111"

    "0"

    "9876543219876"

    Returns: -1

    The infinite string S does contain 9876543219876 consecutive zeroes. However, the first occurrence is too far, thus the string T doesn't contain it.

  6. "1111111111111"

    "1111111"

    "1"

    Returns: -1

  7. "1"

    "1"

    "1"

    Returns: -1

  8. "11111111111111111111111111111111111111111111111111"

    "11111111111111111111111111111111111111111111111111"

    "1"

    Returns: -1

  9. "11111111111111111111111111111111111111111111111111"

    "11111111111111111111111111111111111111111111111111"

    "10000000000000000"

    Returns: -1

  10. "0"

    "0"

    "1"

    Returns: 0

  11. "0"

    "0"

    "47"

    Returns: 0

  12. "0"

    "0"

    "10000000000000000"

    Returns: 0

  13. "0"

    "1"

    "1"

    Returns: 0

  14. "0"

    "1"

    "2"

    Returns: 0

  15. "1"

    "0"

    "1"

    Returns: 1000000

  16. "1"

    "0"

    "2"

    Returns: 2000001

  17. "1"

    "0"

    "87654321"

    Returns: 3929294272158360

  18. "00001010101011101101010100000"

    "000000000010100000100000010000000"

    "4"

    Returns: 0

  19. "00001010101011101101010100000"

    "000000000010100000100000010000000"

    "5"

    Returns: 24

  20. "0000101000000001111100000"

    "1010010010101010"

    "8"

    Returns: 7

  21. "0000101000000001111100000"

    "0000101000000001111100000"

    "9"

    Returns: 20

  22. "10000000000000000000000000000000000000000000000000"

    "00000000000000000000000000000000000000000000000001"

    "98"

    Returns: 49999951

  23. "10000000000000000000000000000000000000000000000000"

    "00000000000000000000000000000000000000000000000001"

    "99"

    Returns: -1

  24. "00000000000000000000000000000000000000000000000001"

    "10000000000000000000000000000000000000000000000000"

    "98"

    Returns: 50000001

  25. "00000000000000000000000000000000000000000000000001"

    "10000000000000000000000000000000000000000000000000"

    "99"

    Returns: -1

  26. "0010100101010101010101001111101011110"

    "000000001111111111111101010111110000000"

    "11"

    Returns: 74000071

  27. "00000"

    "10"

    "5000000"

    Returns: 0

  28. "00000"

    "10"

    "5000001"

    Returns: 5000001

  29. "00000000000000000000000000000000000000000000000000"

    "10000000000000000000000000000000000000000000000000"

    "49876543"

    Returns: 0

  30. "00000000000000000000000000000000000000000000000000"

    "10000000000000000000000000000000000000000000000000"

    "50000049"

    Returns: 50000001

  31. "00000000000000000000000000000000000000000000000000"

    "10000000000000000000000000000000000000000000000000"

    "50000050"

    Returns: -1

  32. "0000000000000000000000"

    "0000000000000000000000000000"

    "4632761373274275"

    Returns: 0

  33. "1"

    "0"

    "140424892"

    Returns: -1

  34. "1"

    "0"

    "140424891"

    Returns: 9999999826968495

  35. "000000000000000000000000000001"

    "00"

    "172237485"

    Returns: 9999997066219256

  36. "000000000000000000000000000001"

    "00"

    "172237511"

    Returns: 9999999695306340

  37. "000000000000000000000000000001"

    "00"

    "172237512"

    Returns: -1

  38. "001010111000"

    "0"

    "49283"

    Returns: 592550136000

  39. "01000"

    "000"

    "51"

    Returns: 80000357

  40. "1"

    "0"

    "2"

    Returns: 2000001

  41. "1"

    "00"

    "3"

    Returns: 2000002

  42. "0111111110"

    "000"

    "235153000"

    Returns: 9999998702205833

  43. "0"

    "00000100000"

    "1000008"

    Returns: 1000006

  44. "00110100110110001000"

    "00"

    "180989878"

    Returns: 9999232272139029

  45. "01100"

    "00"

    "195062491"

    Returns: 9999999678656290

  46. "00000000000000000000000000000000000000000000000000"

    "00010000000000000000000000000000000000000000000100"

    "50000005"

    Returns: 50000048

  47. "1"

    "0"

    "140424892"

    Returns: -1

  48. "00000"

    "010"

    "5000002"

    Returns: 5000002

  49. "0"

    "01"

    "1000001"

    Returns: 0

  50. "1"

    "00"

    "1000"

    Returns: 500249500

  51. "0"

    "010"

    "1000002"

    Returns: 1000002

  52. "111"

    "0"

    "1000"

    Returns: 3000499500

  53. "0"

    "1"

    "100"

    Returns: 0

  54. "0"

    "00"

    "3"

    Returns: 0

  55. "0"

    "1"

    "1000000000000"

    Returns: -1

  56. "000"

    "000"

    "1000000000"

    Returns: 0

  57. "101010"

    "0"

    "1000"

    Returns: 5994498500

  58. "001010"

    "00"

    "123456789"

    Returns: 4180764798634055

  59. "000000"

    "000000"

    "3"

    Returns: 0

  60. "00001111100000000000000000"

    "00000"

    "10000000"

    Returns: 61999851000033

  61. "000100"

    "000"

    "100"

    Returns: 192001486

  62. "00000000000000000000000000000000000000000000000000"

    "00000000000000000000000000000000000000000000000000"

    "10000000000000000"

    Returns: 0

  63. "11111111111111111111111111"

    "0"

    "9876543219876"

    Returns: -1

  64. "01000"

    "00"

    "192500123"

    Returns: 9745324253753537

  65. "00001000001"

    "1111"

    "3"

    Returns: 0

  66. "101"

    "00"

    "150"

    Returns: 225005550

  67. "1"

    "101"

    "1"

    Returns: 1000001

  68. "0000"

    "0001"

    "4000001"

    Returns: 0

  69. "00011"

    "1100"

    "5"

    Returns: 5000002

  70. "000"

    "1"

    "2"

    Returns: 0

  71. "010"

    "0"

    "1000"

    Returns: 2994497502

  72. "0"

    "00100"

    "1000004"

    Returns: 1000003

  73. "0001"

    "10"

    "4"

    Returns: 4000001

  74. "1111111111111111111100000"

    "0"

    "9876543213"

    Returns: -1

  75. "10101010"

    "101010101010"

    "9876578"

    Returns: -1

  76. "10001"

    "10001"

    "999000"

    Returns: -1

  77. "00100"

    "0"

    "4"

    Returns: 3

  78. "1"

    "0"

    "140424891"

    Returns: 9999999826968495

  79. "111010100001010"

    "0"

    "111111111"

    Returns: 7839505977160494

  80. "0010"

    "0000"

    "24000000"

    Returns: 95999987999999

  81. "0010"

    "0000"

    "21000000"

    Returns: 76124989499999

  82. "010110"

    "1111100"

    "3"

    Returns: 6000005

  83. "0011"

    "1100"

    "4"

    Returns: 4000002

  84. "0"

    "010"

    "1000001"

    Returns: 0

  85. "000000000"

    "000000000"

    "111111111"

    Returns: 0

  86. "0"

    "00"

    "1000002"

    Returns: 0

  87. "1"

    "00000000"

    "125"

    Returns: 16000960

  88. "10"

    "00"

    "4"

    Returns: 4000001

  89. "0000000000"

    "000000000"

    "100000000000"

    Returns: 0

  90. "00000000000000000000000000000000000000000000000000"

    "0"

    "999999999999"

    Returns: 0

  91. "0001000"

    "0000000000"

    "1011"

    Returns: 707050497

  92. "1001010010101010100010001010101"

    "1010100101010100100000010101"

    "6"

    Returns: 31000017

  93. "000"

    "000"

    "20"

    Returns: 0

  94. "00100"

    "0000"

    "4004"

    Returns: 5001997998

  95. "0110"

    "0000000000"

    "1000002"

    Returns: 449999499999

  96. "00100"

    "0000"

    "435432"

    Returns: 567984475182

  97. "111010100001010"

    "010000001000"

    "1000000000000000"

    Returns: -1

  98. "0"

    "1"

    "10000000"

    Returns: -1

  99. "0000010101000000"

    "00000000"

    "100000"

    Returns: 200608850002

  100. "00100"

    "00"

    "6"

    Returns: 4999998

  101. "010100"

    "0"

    "10"

    Returns: 42000019

  102. "10000000000000000000000000000000000000000000000000"

    "00000000000000000000000000000000000000000000000001"

    "60"

    Returns: 49999951

  103. "00001000"

    "0000"

    "111554487"

    Returns: 1778659155231557

  104. "101"

    "0"

    "1000"

    Returns: 3000499500

  105. "000"

    "1110001110"

    "3000001"

    Returns: 3000009

  106. "1"

    "0"

    "1000000000000000"

    Returns: -1

  107. "0010"

    "000"

    "11"

    Returns: 12000008

  108. "1111110000"

    "0"

    "20"

    Returns: 160000116

  109. "10"

    "01"

    "2"

    Returns: 1999999

  110. "001010"

    "010101"

    "3"

    Returns: 5

  111. "111"

    "00000"

    "117"

    Returns: 72001380

  112. "01"

    "1000"

    "4"

    Returns: 2000001

  113. "1"

    "1001"

    "2"

    Returns: 1000001

  114. "1111111111111111111111111111111011010101010101000"

    "0"

    "7"

    Returns: 196000003

  115. "1"

    "0000000000"

    "25000"

    Returns: 2531237500

  116. "11001"

    "00"

    "10"

    Returns: 25000020

  117. "011"

    "110"

    "2"

    Returns: 3000002

  118. "0"

    "10000000000"

    "1000001"

    Returns: 1000001

  119. "110"

    "000"

    "1234567"

    Returns: 1488590917442

  120. "1101010010"

    "0001000"

    "3"

    Returns: 9999999

  121. "010"

    "0"

    "3"

    Returns: 2999999

  122. "0"

    "0100"

    "1000003"

    Returns: 1000002

  123. "1"

    "0"

    "10000000000000000"

    Returns: -1

  124. "1"

    "1"

    "1919"

    Returns: -1

  125. "1"

    "0100010"

    "3"

    Returns: 1000002

  126. "100001110000000110000000000"

    "000000000000000"

    "6546212"

    Returns: 13211603572355

  127. "0"

    "10"

    "1000001"

    Returns: 1000001

  128. "0111111110"

    "000"

    "100000"

    Returns: 334996583333

  129. "1"

    "0"

    "9"

    Returns: 9000036

  130. "0"

    "001"

    "1000002"

    Returns: 0

  131. "0000000000"

    "0000100000"

    "10000009"

    Returns: 10000005

  132. "00"

    "0000000000"

    "5"

    Returns: 0

  133. "00100"

    "0000"

    "4"

    Returns: 3

  134. "1001010010100100101001"

    "0001000111010010100000000"

    "12462189"

    Returns: -1

  135. "0"

    "0"

    "1000000000000"

    Returns: 0

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: