Statistics

Problem Statement for "BinarySearch"

Problem Statement

Consider the implementation of binary search shown below: 

def binary_search(array, value):
    low = 0
    high = len(array)-1
    while low <= high:
        mid = (low + high) / 2
        if array[mid] == value: return '1'
        if array[mid] < value: low = mid + 1
        if array[mid] > value: high = mid - 1
    return '0'

Clearly, if the input array is sorted, the procedure returns '1' if the given value is present in the given array and it returns '0' if the value is not in the array.

In this problem we'll take a look at what happens if the array isn't sorted. Even in those cases binary search can sometimes give the correct answer, but sometimes we can search for a value that is present in the array and the search will fail to find it.


Let P be a permutation of numbers from 0 to N-1, inclusive. The signature of P is a string sig(P) of length N defined as follows:
sig(P) = binary_search(P,0) + binary_search(P,1) + ... + binary_search(P,N-1)
In words, character i of the signature of a permutation tells us whether binary search correctly locates the value i in this permutation.


You are given a String S containing N zeros and ones. Count all permutations P of order N such that their signature is S. Return that count modulo 10^9 + 7.

Definition

Class:
BinarySearch
Method:
count
Parameters:
String
Returns:
int
Method signature:
int count(String S)
(be sure your method is public)

Notes

  • In the pseudocode for binary search, the valid indices into an array of length N are values from 0 to N-1, inclusive.
  • Also in the pseudocode, "/" represents integer division that truncates (e.g., 9/2 = 4).

Constraints

  • S will have between 1 and 50 characters, inclusive.
  • Each character of S will be either '0' or '1'.

Examples

  1. "111"

    Returns: 1

    There is only one permutation with this signature: P = {0, 1, 2}. In other words, for N = 3 binary search always works if and only if the input permutation is sorted in increasing order.

  2. "000"

    Returns: 0

    There is no permutation with this signature. I.e., for N = 3 there is no permutation such that binary search always fails.

  3. "101"

    Returns: 2

    The two permutations with this signature are P = {0, 2, 1} and P = {1, 0, 2}.

  4. "100011"

    Returns: 12

  5. "0011101100010010010111010111010"

    Returns: 373885200

  6. "0"

    Returns: 0

  7. "1"

    Returns: 1

  8. "00"

    Returns: 0

  9. "10"

    Returns: 0

  10. "01"

    Returns: 1

  11. "11"

    Returns: 1

  12. "100"

    Returns: 0

  13. "010"

    Returns: 1

  14. "110"

    Returns: 1

  15. "001"

    Returns: 0

  16. "011"

    Returns: 1

  17. "0000"

    Returns: 0

  18. "1000"

    Returns: 0

  19. "0100"

    Returns: 0

  20. "1100"

    Returns: 0

  21. "0010"

    Returns: 2

  22. "1010"

    Returns: 1

  23. "0110"

    Returns: 2

  24. "1110"

    Returns: 1

  25. "0001"

    Returns: 0

  26. "1001"

    Returns: 4

  27. "0101"

    Returns: 4

  28. "1101"

    Returns: 2

  29. "0011"

    Returns: 2

  30. "1011"

    Returns: 3

  31. "0111"

    Returns: 2

  32. "1111"

    Returns: 1

  33. "00000"

    Returns: 0

  34. "10000"

    Returns: 0

  35. "01000"

    Returns: 0

  36. "11000"

    Returns: 0

  37. "00100"

    Returns: 4

  38. "10100"

    Returns: 2

  39. "01100"

    Returns: 4

  40. "11100"

    Returns: 2

  41. "00010"

    Returns: 6

  42. "10010"

    Returns: 6

  43. "01010"

    Returns: 7

  44. "11010"

    Returns: 3

  45. "00110"

    Returns: 6

  46. "10110"

    Returns: 4

  47. "01110"

    Returns: 3

  48. "11110"

    Returns: 1

  49. "00001"

    Returns: 0

  50. "10001"

    Returns: 6

  51. "01001"

    Returns: 8

  52. "11001"

    Returns: 6

  53. "00101"

    Returns: 8

  54. "10101"

    Returns: 6

  55. "01101"

    Returns: 6

  56. "11101"

    Returns: 2

  57. "00011"

    Returns: 6

  58. "10011"

    Returns: 4

  59. "01011"

    Returns: 5

  60. "11011"

    Returns: 3

  61. "00111"

    Returns: 6

  62. "10111"

    Returns: 2

  63. "01111"

    Returns: 3

  64. "11111"

    Returns: 1

  65. "11111111111111111111111111111111111111111111111111"

    Returns: 1

  66. "00000000000000000000000000000000000000000000000000"

    Returns: 0

  67. "00000000000000000010100000100000001010100000000000"

    Returns: 805159173

  68. "01001100000010000000010010010000000000000011010000"

    Returns: 284574371

  69. "01000010100000110000011000010000010101000110000000"

    Returns: 108757553

  70. "11110000001110000011111110110101110001101011000000"

    Returns: 754590874

  71. "00111010001011101001000110100001010100011111010010"

    Returns: 169562051

  72. "11010011110111011110000001101101000010001101001101"

    Returns: 101750443

  73. "11111111001111011111001001111001100101101010101111"

    Returns: 253593247

  74. "10110111011111111101111100101101111011111111101111"

    Returns: 336111964

  75. "11111111111111101110111111111110110110011111111111"

    Returns: 140154068

  76. "0000011001010000000000000001000000010000000000000"

    Returns: 338666891

  77. "0000001000010001000000000000001010101001100000001"

    Returns: 396043826

  78. "0010101000000001000100010001000100000100110100000"

    Returns: 786957552

  79. "1111001000011101001100000011001001010011101100000"

    Returns: 480715588

  80. "0100010111000000001010111000010000111011001111010"

    Returns: 290473414

  81. "1100111011101001101100011111001110011100111001011"

    Returns: 216398492

  82. "1101111011101111111111111000111110111100110001011"

    Returns: 802708929

  83. "1111111001101111111111110101011111101101111111111"

    Returns: 19623514

  84. "1110111111111111111110111111110111101111101111111"

    Returns: 6320868

  85. "100001000001000010000000000001000000000000000100"

    Returns: 286870100

  86. "000000100001010000101010000010001000010100000000"

    Returns: 769090031

  87. "011011000100000100000101000100001010000010011101"

    Returns: 784330660

  88. "000100011100000101100100001011001010001000001010"

    Returns: 296403103

  89. "001000010110110010100000001101001001110111001011"

    Returns: 298918426

  90. "000100111110110110001011110010111010001001110111"

    Returns: 879309899

  91. "110111000111110111110001110111011111111111111111"

    Returns: 358413900

  92. "111111111011111011101111111110001111100111110111"

    Returns: 449086028

  93. "011111111111111111111111111111111111111111111111"

    Returns: 31

  94. "00010000000000000000000000100100000000000000000"

    Returns: 492879102

  95. "00000000000000001000001010000001100000100000000"

    Returns: 695829908

  96. "00000011001111000010100110010101101010101110101"

    Returns: 525539449

  97. "10111011111110111111100111111101111111101101111"

    Returns: 742475379

  98. "0000000000100001000000010000000000000100000000"

    Returns: 193063553

  99. "0011000000000000101000011000000000000000000000"

    Returns: 315651978

  100. "0111100001101001100101011100101101111001011110"

    Returns: 30911112

  101. "1100111111010111000111111010110101111001111110"

    Returns: 239466636

  102. "000000010000000000000000000000000000000000010"

    Returns: 392288437

  103. "100100000000000010000000100001000010000010000"

    Returns: 381311126

  104. "000001010000000010101011110001100110010011110"

    Returns: 600028539

  105. "111000101110111110110110010010111001011111100"

    Returns: 840303746

  106. "00000100000000000000000100000100001010000000"

    Returns: 984138754

  107. "00001000000100000010100010000010000011000010"

    Returns: 739996136

  108. "10000101110001101001110111000001000011010111"

    Returns: 568681569

  109. "11110111011111101111100111101001011111001111"

    Returns: 297519725

  110. "0000100000000010000001100000000000000000010"

    Returns: 13265740

  111. "0011000000010000100000100001000010100010100"

    Returns: 77451083

  112. "0100111101000010010011011111111001100000110"

    Returns: 280692027

  113. "1011110100111111111111111100111000100101111"

    Returns: 191220100

  114. "000000010100010000000000101000001100000010"

    Returns: 809581057

  115. "000000000000010100000001000011000000000000"

    Returns: 846788726

  116. "100110000010101000010101010011011011001001"

    Returns: 667662895

  117. "001001100110111000010010101011000110011101"

    Returns: 420244527

  118. "00010011010000000001000000000000010000000"

    Returns: 389481453

  119. "00100000010000000000000001000000000100010"

    Returns: 895293971

  120. "00110001011001110000001101110110111110101"

    Returns: 626982611

  121. "11111001111011111111101111111101111101011"

    Returns: 205190457

  122. "1101111"

    Returns: 3

  123. "0000100"

    Returns: 48

  124. "000000110100000"

    Returns: 688262400

  125. "111110111011111"

    Returns: 56

  126. "0100100001111011000110110110111"

    Returns: 368188002

  127. "1111101111011100101001110111111"

    Returns: 730133466

  128. "0101010101010101010101010101010101010101010101010"

    Returns: 145599012

  129. "10101010101010101010101010101010101010101010101"

    Returns: 500212141

  130. "001001001001001001001001001001001001001001001"

    Returns: 558213385

  131. "0110011001100110011001100110011001100110011001"

    Returns: 575628658

  132. "1011101110111011101110111011101110111011101110"

    Returns: 368735950

  133. "10100101001010010100101001010010100101001"

    Returns: 106147781

  134. "00110001100011000110001100011000110001100011000110"

    Returns: 735386491

  135. "00000000000000000000000000000000000000000000000000"

    Returns: 0

  136. "10000000000000000000000000000000000000000000000000"

    Returns: 0

  137. "10000000000000000000000000000000000000000000000001"

    Returns: 0

  138. "00000000000000000000000000000000000000000000000001"

    Returns: 0

  139. "0000000000000000000000000000000000000000000000110"

    Returns: 0

  140. "100000000000000000000000000000000000000000000110"

    Returns: 0

  141. "110000000000000000000000000000000000000000000110"

    Returns: 457409939

  142. "100000000000000000000000000000000000010"

    Returns: 0

  143. "11111111111111111111111111111110111111111111111111"

    Returns: 22

  144. "11111111111111111111011111111111111111111111111110"

    Returns: 450

  145. "11111101111111111111111111011111011111111111111111"

    Returns: 14563

  146. "10110111101111111111011111111111111111111111111111"

    Returns: 570904

  147. "01111111111111101111111111011111111111111111101011"

    Returns: 6829712

  148. "11111111111111111011111111111111101111111111111"

    Returns: 520

  149. "11111111111111111111101111111111111110011111111"

    Returns: 8364

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: