Statistics

Problem Statement for "FilipTheFrog"

Problem Statement

Filip the Frog lives on a number line. There are islands at some points on the number line. You are given the positions of these islands in the int[] positions.

Filip starts on the island located at positions[0]. His maximal jump length is L, which means that he can jump to any island that is within a distance of L (inclusive) from his current location. Filip can't jump to a point on the number line that doesn't contain an island. He can make an unlimited number of jumps.

An island is reachable if Filip can get to it through some sequence of jumps. Please find and return the number of reachable islands.

Definition

Class:
FilipTheFrog
Method:
countReachableIslands
Parameters:
int[], int
Returns:
int
Method signature:
int countReachableIslands(int[] positions, int L)
(be sure your method is public)

Notes

  • If two islands are located at points A and B on the number line, then the distance between them is |A - B|.

Constraints

  • positions will contain between 1 and 50 elements, inclusive.
  • Each element of positions will be between 0 and 1000, inclusive.
  • The elements of positions will be distinct.
  • L will be between 1 and 1000, inclusive.

Examples

  1. {4, 7, 1, 3, 5}

    1

    Returns: 3

    Filip starts at position 4 and his maximal jump length is 1. He can reach the islands at positions 3, 4, and 5.

  2. {100, 101, 103, 105, 107}

    2

    Returns: 5

    Here he can reach all 5 islands.

  3. {17, 10, 22, 14, 6, 1, 2, 3}

    4

    Returns: 7

  4. {0}

    1000

    Returns: 1

  5. {0, 499, 999}

    499

    Returns: 2

  6. {1000, 0}

    1000

    Returns: 2

  7. {511, 15, 409, 667, 205, 23, 772, 212, 375, 944, 527, 98, 758, 273, 244, 803, 593, 857, 80, 126, 982, 10}

    157

    Returns: 22

  8. {633, 430, 611, 191, 5, 727, 111, 412, 626, 805, 50, 0, 217, 807, 704, 260, 434, 709, 16, 850, 959, 445, 305, 579, 896, 201, 965, 492, 406, 227, 54, 456, 622, 91, 586, 578, 895, 215, 279, 650}

    103

    Returns: 40

  9. {330, 696, 245, 827, 303, 601, 58, 379, 849, 970, 339, 911, 548, 399, 118, 49, 784, 863, 781, 287, 284, 540, 952, 592, 177, 342, 670, 560, 541, 554, 173, 491, 931, 706, 905, 75, 644, 543, 378, 641, 772, 273, 803, 628, 971}

    90

    Returns: 17

  10. {122, 935, 872, 975, 633, 783, 607, 824, 832, 354, 353, 377, 545, 329, 647, 7, 845, 823, 190, 688, 12, 515, 8, 574, 579, 357, 450, 602, 670, 945, 362, 658, 165, 352, 76, 345, 572, 821, 516, 827, 473, 884, 559, 455}

    188

    Returns: 44

  11. {170, 750, 543, 313, 62, 381, 703, 359, 326, 650, 65, 0, 184, 247, 456, 654, 612, 265, 911, 655, 148, 13, 7, 354, 369, 831, 288, 527, 71, 566, 406, 164, 42, 427, 689, 797, 717, 954, 546, 190, 50, 196, 88, 697, 306, 958, 845, 567, 93, 666}

    91

    Returns: 50

  12. {376, 243, 244, 399, 34, 663, 101, 500, 752, 816, 890, 742, 300, 190}

    45

    Returns: 2

  13. {894, 184, 527, 860, 528, 817, 210, 932, 688, 907, 749, 179, 589, 128, 333, 996, 366, 170, 823, 51, 735, 459, 4, 60, 843, 268, 553, 363, 984, 714, 921, 6, 560, 889, 611, 629, 469, 632, 236, 382, 360, 944, 147, 427, 63, 920, 196, 447, 532}

    128

    Returns: 49

  14. {203, 732, 467, 385, 282, 594, 785, 910, 938, 118, 70, 256, 383, 441, 889, 1000, 728, 599, 492, 499, 539, 105, 198, 494, 91, 612}

    41

    Returns: 2

  15. {814, 681, 306, 188, 437, 158, 257, 8, 505, 764, 128, 260, 533, 145, 982, 559, 252, 849, 530, 855, 411, 981, 446, 830, 717, 918, 630, 955, 476, 148, 300, 758, 852, 2, 513, 183, 414, 44, 567, 735, 450, 659}

    127

    Returns: 42

  16. {457, 638, 66, 867, 589, 523, 758}

    662

    Returns: 7

  17. {372, 907, 699, 564, 988, 764, 535, 931, 380, 742, 592, 261, 527, 804, 413, 321, 387, 71, 763, 628}

    293

    Returns: 20

  18. {686, 294, 101, 364, 340, 44, 667, 854, 76, 877, 295, 627, 639, 568, 334, 621, 506, 407, 393, 29, 977, 33, 678, 710, 802, 313, 601, 12, 876, 431, 227, 816, 119, 860, 700, 336, 129, 990, 140, 164, 542, 347, 477, 13, 256, 799, 937, 352, 878}

    108

    Returns: 49

  19. {7, 65, 635, 27, 86, 129, 192, 816, 699, 688, 702, 20, 729, 520, 160, 312, 790, 875, 402, 239, 469, 676, 685, 196, 690, 544, 742, 328, 914, 806, 975, 265, 542, 386, 263, 946, 68, 396, 911, 111, 774, 921}

    87

    Returns: 23

  20. {562, 985, 399, 266, 728, 541, 246, 937, 63, 402, 979, 271, 326, 638, 83, 677, 739, 313, 35, 23, 93, 933, 831}

    165

    Returns: 23

  21. {393, 247, 507, 489, 459, 756, 152, 694, 224, 368, 704, 714, 948, 600, 206, 849, 64, 20, 231, 81, 397, 933, 566}

    25

    Returns: 3

  22. {836, 662, 923, 491, 759, 208, 885, 365, 974, 133, 708, 72, 416, 80, 752, 524, 323, 64, 24, 607, 927, 227, 812, 496, 351, 334, 515, 513, 861, 423, 53, 722, 939}

    147

    Returns: 33

  23. {880, 312, 759, 982, 744, 995, 342, 699, 889, 591, 348, 518, 682, 216, 864, 77, 427, 138, 313, 708, 34, 528, 33, 385, 746, 246, 917, 439, 599, 271, 0, 656, 827, 493, 563, 275, 714, 838}

    54

    Returns: 6

  24. {87, 443, 339, 777}

    590

    Returns: 4

  25. {257, 347, 335, 661, 908, 651, 687, 990, 228, 430}

    295

    Returns: 10

  26. {989, 844, 321, 352, 123, 707, 762, 770, 722, 960, 588, 900, 732, 630, 318, 445, 309, 545, 500, 25, 864, 525, 564, 432, 587, 846, 828, 498, 965}

    196

    Returns: 29

  27. {706, 789, 340, 610, 836, 422, 70, 675, 573, 130, 73, 533, 113, 613, 703, 148, 278, 919, 30, 458, 327, 227, 219, 396, 376, 134, 687, 867, 178, 460, 499, 774, 170, 715, 468, 329, 306, 926, 634, 590, 971, 450, 68, 211, 922, 20, 214, 518, 386, 869}

    4

    Returns: 2

  28. {990, 835, 974, 345, 202, 226, 406, 26, 751, 834, 727, 885, 499, 888, 609, 476, 929, 964, 932, 188, 412, 250, 400, 301, 954, 17, 128, 754, 871, 666, 801, 391, 947, 77, 167, 42, 687, 648, 158, 64, 320, 482, 213, 292, 745, 34, 420, 480, 610, 760}

    37

    Returns: 7

  29. {571, 176, 385, 812, 290, 117, 365, 146, 554, 47, 271, 433, 605, 754, 311, 438, 325, 486, 102, 368, 787, 921, 506, 753, 767, 371, 37, 173, 519, 78, 976, 125, 348, 698, 529, 889, 277, 171, 637, 716, 603, 295, 302, 52, 48, 709, 354, 167, 694, 160}

    186

    Returns: 50

  30. {111, 142, 593, 12, 499, 126, 876, 868, 650, 389, 758, 909, 606, 514, 658, 750, 684, 94, 218, 543, 62, 123, 752, 823, 144, 946, 244, 226, 998, 676, 709, 809, 172, 386, 858, 678, 364, 428, 332, 375, 267, 448, 1000, 184, 539, 751, 87, 855, 963, 657}

    55

    Returns: 15

  31. {114, 518, 71, 454, 75, 243, 53, 153, 29, 595, 254, 887, 358, 618, 463, 139, 39, 109, 658, 57, 222, 37, 927, 460, 692, 604, 227, 171, 380, 242, 982, 56, 646, 760, 953, 233, 266, 626, 972, 255, 516, 20, 244, 186, 614, 130, 381, 477, 58, 960}

    141

    Returns: 50

  32. {759, 979, 587, 327, 257, 936, 445, 97, 169, 896, 978, 89, 469, 92, 388, 648, 791, 775, 82, 937, 498, 940, 714, 450, 131, 389, 153, 9, 529, 228, 530, 660, 862, 907, 890, 732, 468, 899, 575, 646, 109, 661, 202, 265, 803, 23, 901, 988, 552, 126}

    76

    Returns: 50

  33. {131, 326, 78, 439, 476, 744, 72, 333, 792, 826, 28, 749, 399, 958, 551, 929, 144, 564, 434, 347, 655, 324, 60, 375, 989, 296, 866, 602, 726, 425, 596, 793, 117, 251, 361, 519, 583, 299, 284, 638, 994, 105, 385, 6, 152, 734, 805, 230, 398, 803}

    155

    Returns: 50

  34. {948, 87, 61, 303, 929, 592, 711, 130, 199, 399, 715, 594, 934, 50, 157, 413, 847, 989, 133, 928, 369, 824, 127, 897, 80, 777, 658, 894, 448, 903, 106, 465, 876, 237, 488, 352, 14, 273, 588, 849, 12, 710, 852, 580, 774, 573, 52, 29, 322, 439}

    58

    Returns: 15

  35. {556, 868, 666, 569, 176, 136, 869, 644, 665, 565, 550, 215, 288, 202, 850, 409, 133, 12, 982, 255, 421, 943, 509, 928, 358, 5, 198, 917, 650, 637, 687, 583, 127, 911, 353, 438, 214, 464, 322, 34, 948, 279, 386, 692, 374, 402, 994, 309, 502, 273}

    269

    Returns: 50

  36. {803, 496, 886, 634, 954, 335, 356, 761, 783, 109, 550, 907, 996, 647, 941, 274, 681, 248, 246, 229, 606, 513, 230, 834, 961, 735, 644, 235, 91, 197, 432, 521, 562, 178, 191, 569, 63, 571, 708, 893, 74, 390, 906, 400, 696, 380, 340, 515, 411, 546}

    98

    Returns: 50

  37. {9, 2, 1, 6, 12, 16, 19, 21 }

    3

    Returns: 3

  38. {8, 10, 12, 15, 16, 17, 18 }

    2

    Returns: 3

  39. {4, 10, 11, 12, 13 }

    1

    Returns: 1

  40. {16, 8, 9, 12 }

    1

    Returns: 1

  41. {1, 4, 9, 12 }

    3

    Returns: 2

  42. {1, 10, 4, 7 }

    3

    Returns: 4

  43. {5, 1, 2 }

    2

    Returns: 1

  44. {1, 2, 3, 4 }

    1

    Returns: 4

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

    1

    Returns: 9

  46. {1, 5, 1000 }

    1

    Returns: 1

  47. {6, 1, 2 }

    1

    Returns: 1

  48. {100, 1, 2, 3, 4, 5, 6, 7, 8 }

    2

    Returns: 1

  49. {1, 2 }

    3

    Returns: 2

  50. {0, 1, 2, 3, 100, 101, 102, 103 }

    1

    Returns: 4

  51. {16, 8, 9, 12 }

    4

    Returns: 4

  52. {1, 1000, 800, 999, 200, 998, 3 }

    1

    Returns: 1

  53. {8, 6, 5, 4, 3, 2, 1 }

    1

    Returns: 1

  54. {4, 1, 2, 6, 7 }

    1

    Returns: 1

  55. {1, 10, 20, 30 }

    4

    Returns: 1

  56. {17, 10, 22, 14, 6, 1, 2, 3, 600 }

    4

    Returns: 7

  57. {10, 1, 2, 3, 4, 11 }

    1

    Returns: 2

  58. {1 }

    1

    Returns: 1

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

    1

    Returns: 1

  60. {100 }

    1

    Returns: 1

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: