Statistics

Problem Statement for "FindBob"

Problem Statement

There is a street. There are N houses along the street. The houses are numbered from 0 to N-1, in order.

Your friend Bob lives in one of these houses. You want to find him.


You already stopped at some (possibly zero) of the houses and asked "Does Bob live here?" Each time the answer you received was "You are X houses away from Bob's house." for some X.

The answers you received are given in the int[] houses. If houses[i] = -1, you weren't in house i yet. Otherwise, houses[i] is the (non-negative integer) answer you were given in house i.


Return a int[] containing all possible locations of Bob's house, assuming all the information you received was correct. (In other words, you should output a house number if and only if this house is consistent with all the distances you were told.)

The return value must be sorted in ascending order (i.e., smaller numbers go first).

Definition

Class:
FindBob
Method:
find
Parameters:
int, int[]
Returns:
int[]
Method signature:
int[] find(int N, int[] houses)
(be sure your method is public)

Constraints

  • N will be between 1 and 50, inclusive.
  • houses will have exactly N elements.
  • Each element of houses will be between -1 and N-1, inclusive.

Examples

  1. 6

    {-1, -1, -1, -1, -1, -1}

    Returns: {0, 1, 2, 3, 4, 5 }

    You haven't been to any of the houses yet. Bob can live anywhere on this street.

  2. 6

    {-1, -1, -1, 2, -1, -1}

    Returns: {1, 5 }

    You went to house #3 and you learned that Bob lives two houses away. This leaves us with just two options: house #1 or house #5. Recall that the return value must be sorted in ascended order. Returning {5, 1} is incorrect.

  3. 6

    {1, -1, -1, 2, -1, -1}

    Returns: {1 }

    In this scenario you also went to house #0. The two pieces of information you have together tell you that Bob must live in house #1.

  4. 6

    {-1, -1, -1, -1, 3, -1}

    Returns: {1 }

    Even though you only went to one house, the information they gave you already revealed the exact location of Bob's house. (The street has no house #7. House #1 is the only house that is 3 houses away from house #4.)

  5. 6

    {-1, -1, -1, -1, 0, -1}

    Returns: {4 }

    Here you got lucky and found Bob immediately.

  6. 6

    {5, -1, -1, -1, -1, 5}

    Returns: { }

    You visited the houses at both ends of the street. In each of them the owner claimed that Bob lives on the other end of the street. They cannot both be correct. As the information you got is contradictory, there correct output is empty: there is no house that would be consistent with all the distances you were told.

  7. 1

    {-1}

    Returns: {0 }

  8. 1

    {0}

    Returns: {0 }

  9. 7

    {-1, -1, -1, -1, 3, -1, -1}

    Returns: {1 }

  10. 9

    {6, -1, -1, -1, 5, -1, 8, -1, -1}

    Returns: { }

  11. 8

    {7, 0, -1, -1, 0, -1, -1, -1}

    Returns: { }

  12. 7

    {-1, 3, 4, -1, 1, -1, -1}

    Returns: { }

  13. 9

    {-1, -1, -1, -1, -1, -1, -1, -1, 0}

    Returns: {8 }

  14. 7

    {-1, -1, 4, -1, 4, -1, -1}

    Returns: { }

  15. 5

    {-1, 0, -1, -1, -1}

    Returns: {1 }

  16. 7

    {-1, -1, -1, -1, 2, -1, -1}

    Returns: {2, 6 }

  17. 8

    {-1, 4, -1, -1, -1, 3, -1, 3}

    Returns: { }

  18. 3

    {-1, 2, -1}

    Returns: { }

  19. 5

    {-1, -1, 2, 0, 4}

    Returns: { }

  20. 6

    {-1, -1, 3, -1, 1, -1}

    Returns: {5 }

  21. 3

    {-1, 1, 2}

    Returns: {0 }

  22. 4

    {0, 0, -1, -1}

    Returns: { }

  23. 6

    {2, -1, -1, 3, 4, -1}

    Returns: { }

  24. 6

    {-1, -1, -1, 5, 4, 5}

    Returns: { }

  25. 7

    {-1, 4, -1, -1, -1, -1, -1}

    Returns: {5 }

  26. 5

    {-1, 3, -1, 1, -1}

    Returns: {4 }

  27. 5

    {-1, 0, -1, -1, -1}

    Returns: {1 }

  28. 7

    {3, -1, -1, 2, -1, 0, -1}

    Returns: { }

  29. 3

    {-1, 0, -1}

    Returns: {1 }

  30. 2

    {-1, 0}

    Returns: {1 }

  31. 5

    {-1, -1, -1, 4, 4}

    Returns: { }

  32. 2

    {0, -1}

    Returns: {0 }

  33. 10

    {3, -1, -1, -1, -1, -1, -1, -1, -1, 0}

    Returns: { }

  34. 8

    {-1, 0, -1, -1, -1, -1, -1, -1}

    Returns: {1 }

  35. 6

    {-1, -1, 4, -1, -1, -1}

    Returns: { }

  36. 5

    {-1, 4, -1, -1, 2}

    Returns: { }

  37. 3

    {2, 0, -1}

    Returns: { }

  38. 8

    {-1, 2, -1, -1, -1, -1, -1, 4}

    Returns: {3 }

  39. 10

    {-1, -1, -1, -1, -1, -1, -1, 0, -1, -1}

    Returns: {7 }

  40. 2

    {-1, 1}

    Returns: {0 }

  41. 10

    {-1, -1, -1, -1, -1, 2, -1, -1, -1, -1}

    Returns: {3, 7 }

  42. 7

    {3, -1, -1, -1, -1, -1, -1}

    Returns: {3 }

  43. 3

    {-1, 0, 1}

    Returns: {1 }

  44. 10

    {-1, -1, -1, 3, 4, -1, -1, -1, 8, -1}

    Returns: {0 }

  45. 2

    {1, 0}

    Returns: {1 }

  46. 3

    {-1, 1, 0}

    Returns: {2 }

  47. 10

    {-1, -1, -1, -1, 1, -1, 1, -1, -1, 4}

    Returns: {5 }

  48. 5

    {0, -1, 2, -1, 4}

    Returns: {0 }

  49. 8

    {-1, 4, -1, -1, -1, -1, -1, -1}

    Returns: {5 }

  50. 8

    {0, -1, -1, -1, -1, 5, -1, -1}

    Returns: {0 }

  51. 8

    {-1, -1, -1, 1, 0, -1, -1, -1}

    Returns: {4 }

  52. 5

    {-1, -1, -1, 1, -1}

    Returns: {2, 4 }

  53. 7

    {-1, 1, -1, 3, 4, -1, -1}

    Returns: {0 }

  54. 2

    {-1, 0}

    Returns: {1 }

  55. 10

    {-1, -1, -1, -1, 5, -1, -1, -1, -1, -1}

    Returns: {9 }

  56. 3

    {0, 1, -1}

    Returns: {0 }

  57. 7

    {-1, 2, -1, -1, 1, -1, -1}

    Returns: {3 }

  58. 10

    {5, -1, -1, -1, -1, -1, -1, -1, 3, -1}

    Returns: {5 }

  59. 8

    {7, -1, 5, -1, -1, -1, 1, -1}

    Returns: {7 }

  60. 4

    {1, -1, -1, 2}

    Returns: {1 }

  61. 2

    {1, -1}

    Returns: {1 }

  62. 8

    {-1, 1, -1, -1, -1, -1, -1, -1}

    Returns: {0, 2 }

  63. 10

    {-1, -1, -1, -1, -1, -1, 6, 7, -1, -1}

    Returns: {0 }

  64. 9

    {-1, 4, -1, -1, -1, -1, 1, -1, 3}

    Returns: {5 }

  65. 3

    {-1, 0, -1}

    Returns: {1 }

  66. 10

    {-1, -1, 7, -1, -1, -1, -1, -1, -1, -1}

    Returns: {9 }

  67. 9

    {-1, 6, -1, -1, -1, -1, 1, -1, -1}

    Returns: {7 }

  68. 10

    {-1, -1, -1, 2, -1, 0, 1, -1, -1, -1}

    Returns: {5 }

  69. 46

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 37}

    Returns: {8 }

  70. 47

    {-1, -1, -1, -1, -1, -1, 35, -1, -1, -1, -1, -1, -1, -1, -1, -1, 25, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, -1, -1, -1}

    Returns: {41 }

  71. 47

    {-1, 21, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {22 }

  72. 46

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 28, -1, -1, -1, -1, 33, -1, -1, 36, -1, -1, -1, -1}

    Returns: {5 }

  73. 48

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 26, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 13, -1, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {45 }

  74. 41

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, -1, -1, -1, 12, -1, -1, 15, -1, -1, -1, -1, -1, -1, 22, -1, -1, -1, -1, -1, 28, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {3 }

  75. 49

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, 25, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 37, 38, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {0 }

  76. 50

    {-1, -1, -1, -1, 19, -1, 17, -1, -1, -1, 13, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 14, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {23 }

  77. 41

    {-1, -1, -1, -1, -1, 6, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {11 }

  78. 48

    {-1, -1, -1, -1, 42, -1, -1, -1, -1, -1, 36, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {46 }

  79. 41

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15, -1, -1, 12, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {37 }

  80. 41

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 17, -1, -1, -1, -1, 22}

    Returns: {18 }

  81. 41

    {-1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 29, -1, -1, -1, -1, -1}

    Returns: {6 }

  82. 42

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 15, -1, -1, -1, -1, -1, -1, 22, -1, -1, -1, -1, 27, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {5 }

  83. 48

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 21, -1, -1, -1, -1, 16, -1, -1, -1, -1, -1, 10, -1, -1, -1, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1}

    Returns: {43 }

  84. 47

    {-1, 42, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 17, -1, -1, -1, -1, 12, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3}

    Returns: {43 }

  85. 43

    {-1, -1, -1, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 24, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 35, -1, -1, -1, -1}

    Returns: {3 }

  86. 47

    {-1, -1, -1, 4, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 14, -1, -1, -1, -1, -1, 20, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {7 }

  87. 42

    {-1, -1, -1, -1, -1, -1, -1, 23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 0, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {30 }

  88. 43

    {-1, 39, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {40 }

  89. 47

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1, -1, -1, -1, -1, -1, -1, -1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 34, -1, -1, -1}

    Returns: {9 }

  90. 41

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {0, 38 }

  91. 40

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 12, 13, -1, -1, 16, -1, -1, -1, -1, -1, 22, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 35, -1, -1, -1, -1}

    Returns: {0 }

  92. 45

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 20, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 31, -1, -1, -1, -1, -1}

    Returns: {8 }

  93. 40

    {-1, -1, -1, -1, -1, -1, -1, 31, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, 12, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {38 }

  94. 46

    {-1, -1, 20, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, -1, -1, -1, -1, 14, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {22 }

  95. 47

    {-1, -1, -1, 14, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {17 }

  96. 40

    {-1, -1, -1, -1, -1, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 11, -1, -1, 14, -1, -1, -1, -1, -1, -1, 21, -1, -1, -1, -1, -1, -1}

    Returns: {12 }

  97. 45

    {-1, -1, -1, -1, 36, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 19, -1, -1, -1, -1, -1, -1, 12, -1, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {40 }

  98. 44

    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}

    Returns: {10, 16 }

  99. 50

    {13, 26, 29, 49, 11, 17, -1, 6, 37, 35, -1, 15, 33, 12, 33, 22, 29, 12, 20, 24, 1, 42, 40, 36, 25, 19, 33, 21, -1, 5, 0, 18, 49, 2, 37, 12, 32, 38, -1, 1, 34, 36, 2, 23, 47, 28, 11, 4, 16, 42}

    Returns: { }

  100. 50

    {39, 24, 31, 21, 1, 3, 18, 37, 44, 18, 2, 38, 27, 28, 25, 45, 45, 20, 45, 4, 15, 25, 22, 5, 44, 23, 23, 10, 17, 0, 0, 35, 42, 35, 11, 7, 34, 13, 4, -1, 26, 26, 25, 44, 26, 36, 45, 7, 8, 48}

    Returns: { }

  101. 50

    {45, 46, 46, 23, 33, 40, 28, 15, 39, 40, 8, 3, 1, 36, 14, 45, 36, 7, 3, 0, 7, 6, 32, 48, 7, 38, 17, 35, 37, 25, 34, 46, 30, 38, 36, 0, 9, 49, 37, 33, 36, 39, 45, 8, 13, 6, 8, 17, 38, 29}

    Returns: { }

  102. 50

    {40, 30, 28, 37, 18, 25, 47, 27, 37, 10, -1, 26, 49, 30, 30, 45, 25, 20, 22, 34, 18, 18, 24, 23, 1, 38, 47, 32, 16, 8, 28, 24, 5, 48, 41, 5, 36, 1, 22, 39, 20, 41, 42, 35, 47, 8, -1, 15, 21, 9}

    Returns: { }

  103. 50

    {38, 1, 25, 29, 44, 19, 8, 16, 15, 20, 25, 41, 6, 12, 41, 10, 38, 13, 17, 41, 14, 28, 43, 48, 32, 20, 8, 32, 22, 6, 8, 10, 35, 13, 33, 35, 49, 32, 48, 19, 39, 49, 39, 33, 12, 49, 39, 14, 1, 22}

    Returns: { }

  104. 50

    {23, 47, 10, 30, 37, 45, 45, 9, 11, 24, 45, 41, 2, 29, 19, 34, 33, 3, 15, 5, 7, 41, 31, 46, 36, 41, 12, 16, 37, 23, 6, 15, 34, 21, 6, 23, 22, 40, 33, 13, 17, 15, 37, 42, 43, 40, 19, 35, 1, 47}

    Returns: { }

  105. 50

    {38, 12, 17, 27, 48, 19, 47, 6, 8, 36, 10, 15, 20, 16, 5, 17, 12, 1, 47, 16, 38, 40, 12, 11, 42, 30, 30, 3, 23, 40, 0, 40, 48, 36, 8, 5, 25, 18, 13, 25, 47, 11, 4, 12, 40, 39, 41, 13, 34, 4}

    Returns: { }

  106. 50

    {34, 25, 18, 19, 22, 6, 4, 43, 19, 28, 12, 48, 6, 40, 4, 33, 41, 20, 47, 35, 43, 29, 49, 13, 2, 19, 18, 49, 45, 46, 41, 49, 23, 15, 48, 36, 2, 3, 15, 28, 31, 13, 31, 31, 30, 17, 19, 26, 32, 14}

    Returns: { }

  107. 50

    {38, 42, 43, 40, 20, 35, 39, 12, 35, 10, 11, 14, 47, 1, 0, 43, 37, 31, 37, 15, 46, 37, 17, 11, 20, 36, 37, 39, 34, 20, 31, 10, 46, 48, 19, 22, 10, 9, 41, 45, 30, 3, 1, 24, 28, 43, 27, 17, 38, 5}

    Returns: { }

  108. 50

    {49, 39, 43, 30, 39, 16, 20, 17, 43, 12, 43, 26, 3, 15, 38, 23, 19, 28, 17, 9, 14, 10, 22, 13, 18, 1, 12, 43, 35, 29, 0, 21, -1, 39, 17, 16, 34, 25, 47, 32, 14, 28, 28, 2, 4, 45, 7, 45, 24, 27}

    Returns: { }

  109. 6

    {-1, -1, 0, -1, 0, -1}

    Returns: { }

  110. 7

    {-1, 1, -1, -1, 2, -1, -1 }

    Returns: {2 }

  111. 6

    {0, -1, 1, 0, -1, -1 }

    Returns: { }

  112. 2

    {0, 0 }

    Returns: { }

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: