Statistics

Problem Statement for "RunningAroundPark"

Problem Statement

Alice went jogging around the park yesterday. There is a circular track around the park, and Alice's house is right next to the track. Alice ran in the clockwise direction. She both started and ended her run at her house. In other words, she completed some positive number of full laps.

There are N trees along the track. The trees are numbered 1 through N in the order in which Alice encounters them when running a single lap. You are given the int N.

Alice remembers some trees she saw during her run. She remembers them in the order in which she encountered them. You are given this information as a int[] d.

For example, d={6,6,1} has the following meaning:

  • Alice started running.
  • After some time she encountered the tree number 6.
  • After some more time she encountered the tree number 6.
  • Even later she encountered the tree number 1.

Compute and return the smallest possible number of laps Alice completed.

Definition

Class:
RunningAroundPark
Method:
numberOfLap
Parameters:
int, int[]
Returns:
int
Method signature:
int numberOfLap(int N, int[] d)
(be sure your method is public)

Constraints

  • N will be between 2 and 50, inclusive.
  • d will contain between 1 and 50 elements.
  • Each element of d will be between 1 and N, inclusive.

Examples

  1. 3

    {1,2,3}

    Returns: 1

    It is possible that Alice ran just a single lap and remembered all the trees she saw.

  2. 24

    {6,6}

    Returns: 2

    Alice ran past the tree number 6 at least twice, so there must have been at least two laps.

  3. 3

    {3,2,1}

    Returns: 3

  4. 50

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

    Returns: 2

  5. 2

    {1}

    Returns: 1

  6. 36

    {2,36,9,30,25,19,29,7,6,8,5,16,11,35,19,6,35,25,15,9,32,23,34,35,11,22,2,1,33,31,7,11,18,28,7,3,13}

    Returns: 21

  7. 41

    {23,18,9,13,1,40}

    Returns: 4

  8. 21

    {18,8,5,11,6,14,13,5,4,6,8,11,9,19,10,20,18,16,15,1}

    Returns: 13

  9. 7

    {3,6,4,5,2,1,3,5,3,3,4,5,1,5,2,7,5,6,3,2,3,1,2,4,4,2,4,5,2,1,2,6,4,1,3,2,7,7,3,3,4,5}

    Returns: 22

  10. 20

    {13,12,14,4,6,8,4,9,9,6,17,4,17,12,14,19,5,13,9,11,1,1,11,13,2,6,13,2,18,4,3,10}

    Returns: 16

  11. 10

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

    Returns: 17

  12. 11

    {11,4,10,7,2,6,11}

    Returns: 4

  13. 45

    {33,24,28,17,4,43,43}

    Returns: 5

  14. 16

    {15,13,15,2,14,6,13,12,2,11,3,13,15,1,6,9,12,13,10,6,12,4,4,9,6,11,10,6,13,8,16,3,7,14,11,5,9,4,1,16,8,14,6}

    Returns: 23

  15. 42

    {7,6,29,19,22,15,25,14,35,33,3,31,23,17,8}

    Returns: 10

  16. 36

    {19}

    Returns: 1

  17. 35

    {14,34,21,16,2,8,23,11,34,32,9,25,30,24,16,8,23,15,19,27,10,11,18,29,32,4,2,16,11,1,11,9,29,13,25,21,27,11,4,21,7,8,16,16,30,29,26,3}

    Returns: 26

  18. 22

    {17,21,12,4,13,18,12,5,20,8,6,17,20,16,4,20,5,19,9,1,6,2,17,22,15,6,11,19,4}

    Returns: 16

  19. 18

    {7,9,8,13,6,17,4,15,2,18,11,14,11,4,12,13,4,8,1,18,9,8,18,4,15,10,3,10,7,14,7,1,14,17,8,8,8,1,3,11,11,16}

    Returns: 23

  20. 34

    {5,14,5,32,30,4,15,11,32,15,17,9,21,12,6,15,20,3,29,28,29,23,12,22,18,8,17,26,34,18,5,18,19,4,17,9,13,26,12,31,18,14,12,26,8,11,29}

    Returns: 24

  21. 18

    {9,8,14,2,18,12,5,18}

    Returns: 5

  22. 11

    {8,5,11,11,2,7,9,1,4,11,2,6,7,7,5,10,11,9}

    Returns: 9

  23. 9

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

    Returns: 26

  24. 30

    {24,28,18,16,19,16,13,3,5,4,27,25,18,5,21,27,4,24,24,24,24,2,17,22,4,4,26,25,2,24,12,20,3,19,24,13,23,2,2,12,28,26,7,29,14,6,18,12}

    Returns: 29

  25. 41

    {9,38,8,26,17,23,41,29,26,29,16,38,37,17}

    Returns: 8

  26. 41

    {31,40,20,17,16,21,12,5,3,22,22,13,33,31,15,39,7,28,22,13,11,13,30,41,8,38,1,20,5,39,11,32,1,11,21,19,8,26,7,40,8,37,28,28,13,31,9,10,38,37}

    Returns: 29

  27. 14

    {11,7,7,12,3,12,5,13,8,4,7,8,10,12,12,4,2,3,4,8,2,2,2,11,10,9,7,5,6,3,14,1,7,13,8,9,1,1,11,13,10,4,2,6,9,9,12,4,10,7}

    Returns: 28

  28. 12

    {3,9,9,6,1,12,4,4,10,10,8,11,7,7,4,12,2,5,11,8,7,8,7,8,4,10,9,6,1,8,10,9,3,3,3,12,12,3,1,7,12,2,5,11,4,8,7,5,6,11}

    Returns: 30

  29. 6

    {4,3,6,3,5,2,5,2,4,6,4,1,6,4,4,1,4,6,1,6,6,1,5,6,3,5,4,6,2,6,6,6,3,5,6,6,3,4,5,1,3,5,3,4,3,6,3,5,4,1}

    Returns: 27

  30. 40

    {39,3,3,25,5,21,6,9,34,13,34,11,26,1,28,2,36,36,26,3,28,29,17,12,30,8,20,10,40,26,10,34,31,32,8,16,1,39,26,18,24,29,5,36,4,37,7,12,1,6}

    Returns: 27

  31. 3

    {1, 2, 3 }

    Returns: 1

  32. 3

    {3, 2, 1 }

    Returns: 3

  33. 4

    {3, 3, 3, 3 }

    Returns: 4

  34. 3

    {1 }

    Returns: 1

  35. 2

    {1, 1, 1, 1, 1 }

    Returns: 5

  36. 24

    {6, 6 }

    Returns: 2

  37. 4

    {3, 2, 1, 3, 2, 1, 3, 2, 1 }

    Returns: 7

  38. 7

    {7, 6, 5, 4, 3, 2, 1 }

    Returns: 7

  39. 40

    {1, 2, 3 }

    Returns: 1

  40. 5

    {3 }

    Returns: 1

  41. 6

    {6, 6, 6, 3, 3 }

    Returns: 5

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: