Statistics

Problem Statement for "JumpGame"

Problem Statement

You are playing a board game that involves your piece jumping around the board. The board is divided up into squares. Each square has a number describing its location called its PLACE. Upon landing on a particular square you are given another number called its DESTINATION. DESTINATION tells you which PLACE to jump to next. Play for a particular piece could go as follows: 

Board: 
  1   3   2   1     DESTINATIONs
|---|---|---|---|
| 0 | 1 | 2 | 3 |   PLACEs
|---|---|---|---|

The leftmost square has PLACE number 0 and DESTINATION number 1. The second square has PLACE number 1 and DESTINATION number 3. The third square has PLACE number 2 and DESTINATION number 2. The last square has PLACE number 3 and DESTINATION number 1. Your piece could start on PLACE 0. PLACE 0 sends you to PLACE 1. PLACE 1 sends you to PLACE 3. PLACE 3 sends you to PLACE 1 and you could loop forever.

You will be given the board specifications and a target PLACE on the board. Your method will return all of the PLACEs that, over the course of the game, would eventually lead you to the target PLACE. Using the previously mentioned board, a target PLACE of 3 would return {0,1,3} since 0, 1, and 3 will all eventually lead to PLACE 3. Starting on a PLACE does count as landing on that particular PLACE, so the result will always include the target value.

The returned values should be sorted in ascending order and contain no duplicate values.

Create a class JumpGame that contains the method whichOnes, which takes a int[] boardSpec, and a int target, and returns a int[] containing all of the PLACEs on the board that will eventually lead to target.

Definition

Class:
JumpGame
Method:
whichOnes
Parameters:
int[], int
Returns:
int[]
Method signature:
int[] whichOnes(int[] boardSpec, int target)
(be sure your method is public)

Notes

  • The value of boardSpec[PLACE] refers to the DESTINATION of PLACE.
  • The PLACEs of the board are equivalent to the indices of boardSpec.
  • Make sure the returned int[] is in ascending order and contains no duplicate values.

Constraints

  • boardSpec contains between 1 and 50 elements, inclusive.
  • The elements of boardSpec are between 0 and the number of elements in boardSpec - 1, inclusive.
  • target is between 0 and the number of elements in boardSpec - 1, inclusive.

Examples

  1. {0,1,2,3,3,3,3}

    6

    Returns: { 6 }

    The only PLACE that eventually leads to 6 is PLACE 6. Note that this does count even though immediately after being on 6 you will jump to PLACE 3.

  2. {0,1,2,3,3,3,3}

    3

    Returns: { 3, 4, 5, 6 }

    If you are on PLACE 3 you are already at the target so it is included in the result set. All PLACEs greater than 3 will jump to 3 immediately thus they all are included as well.

  3. {1,2,3,4,5,6,7,8,0,9}

    4

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8 }

  4. {1,2,3,4,5,6,7,8,0,9}

    9

    Returns: { 9 }

  5. {9,8,7,6,5,4,3,2,1,0}

    6

    Returns: { 3, 6 }

  6. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,0}

    49

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

  7. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,0}

    0

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

  8. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,0}

    23

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

  9. {49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49}

    4

    Returns: { 4 }

  10. {49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49,49}

    49

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

  11. {3,3,3,4,4,4}

    3

    Returns: { 0, 1, 2, 3 }

  12. {3,3,3,4,4,4}

    4

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

  13. {1,1,1,1,1,1,1}

    2

    Returns: { 2 }

  14. {3,3,3,4,4,4}

    5

    Returns: { 5 }

  15. {1,2,1,3}

    3

    Returns: { 3 }

  16. {1,2,3,4,3,5}

    5

    Returns: { 5 }

  17. {5,2,6,3,1,1,0,5}

    5

    Returns: { 0, 1, 2, 4, 5, 6, 7 }

  18. {1,2,3,4,5,6,7,8,0,9}

    4

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8 }

  19. {1,2,3,1}

    3

    Returns: { 0, 1, 2, 3 }

  20. {1,2,3,1,4}

    4

    Returns: { 4 }

  21. {1,3,1,2,4,5}

    5

    Returns: { 5 }

  22. {1,2,3,1,4}

    4

    Returns: { 4 }

  23. {1,2,3,0}

    0

    Returns: { 0, 1, 2, 3 }

  24. {0,1,2,3,3,3,3}

    6

    Returns: { 6 }

  25. {9,8,7,6,5,4,3,2,1,0}

    6

    Returns: { 3, 6 }

  26. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,3}

    29

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 }

  27. {3,2,3,3}

    3

    Returns: { 0, 1, 2, 3 }

  28. {0,1,2,3,3,3,3}

    6

    Returns: { 6 }

  29. {1,0,1,0,4}

    4

    Returns: { 4 }

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: