Statistics

Problem Statement for "CongruenceLock"

Problem Statement

A CongruenceLock is a lock which works as follows. It displays a current status which is a number between 0 and 99999, inclusive. The lock opens if a specific status is reached. There are a number of buttons, each labeled with a number between 1 and 99999, inclusive. When a button labeled with the number b is pressed, the new status of the lock becomes (current status + b) mod 100000.

Given an int current, the current status of the lock, an int target, the status at which the lock opens, and a int[] buttons, the numbers labeled on the buttons, return the minimum number of button presses necessary to open the lock. If it is not possible to open the lock, return -1 instead. Each button can be pressed multiple times.

Definition

Class:
CongruenceLock
Method:
minPushes
Parameters:
int, int, int[]
Returns:
int
Method signature:
int minPushes(int current, int target, int[] buttons)
(be sure your method is public)

Notes

  • In C++, C#.NET and Java, the expression (a + b) mod 100000 can be written as (a + b) % 100000.
  • In VB.NET, the expression (a + b) mod 100000 can be written as (a + b) Mod 100000.

Constraints

  • current is between 0 and 99999, inclusive.
  • target is between 0 and 99999, inclusive.
  • buttons contains between 1 and 50 elements, inclusive.
  • Each element of buttons is between 1 and 99999, inclusive.

Examples

  1. 10000

    10004

    {1}

    Returns: 4

    The button labeled with "1" is pushed 4 times.

  2. 99880

    89

    {100, 3}

    Returns: 5

    The button labeled with "100" is pushed 2 times and the button labeled with "3" is pushed 3 times.

  3. 11111

    22222

    {4, 6, 2222, 3456}

    Returns: -1

  4. 0

    1

    {3}

    Returns: 66667

  5. 172

    172

    {1, 2, 3, 5, 7}

    Returns: 0

  6. 38357

    93452

    {4}

    Returns: -1

  7. 92631

    2564

    {5}

    Returns: -1

  8. 86978

    64571

    {65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2}

    Returns: -1

  9. 86978

    64571

    {65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}

    Returns: 9

  10. 37633

    61446

    {5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 625, 3125, 15625, 78125}

    Returns: -1

  11. 83007

    83007

    {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, 50}

    Returns: 0

  12. 62545

    62573

    {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, 50}

    Returns: 1

  13. 43844

    43823

    {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, 50}

    Returns: 2000

  14. 36557

    9326

    {17231}

    Returns: 89999

  15. 56834

    95061

    {17}

    Returns: 8131

  16. 0

    19843

    {7695, 56922}

    Returns: 14233

  17. 51598

    0

    {55204, 27299, 14629}

    Returns: 533

  18. 58935

    87120

    {79843, 79844, 79845, 79846, 79847, 79848, 79849, 79850, 79851, 79852, 79853, 79854, 79855, 79856, 79857, 79858, 79859, 79860, 79861, 79862, 79863, 79864, 79865, 79866, 79867, 79868, 79869, 79870, 79871, 79872, 79873, 79874, 79875, 79876, 79877, 79878, 79879, 79880, 79881, 79882, 79883, 79884, 79885, 79886, 79887, 79888}

    Returns: 78

  19. 81062

    10475

    {50639}

    Returns: 79467

  20. 6422

    88992

    {59849, 63224}

    Returns: 305

  21. 47039

    21132

    {8736, 18181, 82510}

    Returns: 63

  22. 63803

    29610

    {522, 94656, 28178, 41140}

    Returns: -1

  23. 63803

    17894

    {522, 94656, 28178, 41140}

    Returns: -1

  24. 11883

    40149

    {70449, 94703, 13, 43543, 2042}

    Returns: 23

  25. 97386

    24570

    {31204, 92273, 54741, 46796, 22794, 14590}

    Returns: 14

  26. 68561

    52644

    {23638, 36238, 37466, 1025, 86512, 67429, 98427}

    Returns: 15

  27. 55856

    50841

    {23050, 32401, 66209, 45361, 97726, 60912, 40251, 41269}

    Returns: 7

  28. 338

    63576

    {26360, 98147, 70054, 81100, 39820, 87724, 95690, 49839, 15226}

    Returns: 9

  29. 31802

    65632

    {47317, 69377, 32853, 14746, 67804, 19886, 66584, 84162, 37813, 98985}

    Returns: 11

  30. 41883

    23876

    {6161, 23424, 32858, 63991, 90367, 10638, 90350, 83391, 80691, 71451, 23211, 63292, 62018, 67926, 78518, 76992, 31156, 24858, 19187, 533}

    Returns: 5

  31. 26275

    55453

    {72473, 95393, 47376, 5163, 89255, 92623, 88335, 80843, 93660, 6637, 8578, 57651, 91880, 19216, 42879, 70149, 94783, 14330, 88236, 52953, 71224, 51040, 31471, 48216, 82195, 51205, 62279, 82728, 3793, 91088}

    Returns: 5

  32. 1527

    9848

    {88193, 81427, 75736, 75694, 64639, 51456, 69354, 66152, 60034, 21883, 52910, 74126, 64761, 23059, 68909, 79090, 11295, 21862, 45191, 62334, 48209, 93406, 44530, 94291, 50563, 22135, 98083, 41651, 62952, 69225, 23009, 51146, 45529, 93621, 21717, 5045, 45077, 85947, 71197, 99987}

    Returns: 4

  33. 13735

    15549

    {72590, 42042, 37900, 46557, 53336, 59761, 91747, 10548, 2848, 80031, 49954, 97138, 30594, 72088, 95221, 67121, 35040, 59323, 85006, 81062, 4852, 73504, 2779, 9896, 13458, 88726, 75969, 13446, 91432, 94952, 87558, 64023, 36994, 25458, 5457, 90330, 80096, 97204, 878, 77820, 77235, 50831, 74958, 2706, 17796, 65056, 64703, 52835, 24379, 49709}

    Returns: 3

  34. 0

    99999

    {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,50}

    Returns: 2000

  35. 0

    99999

    {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536}

    Returns: 10

  36. 1

    2

    { 2 }

    Returns: -1

  37. 0

    1

    { 99999 }

    Returns: 99999

  38. 99999

    99997

    { 99999, 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, 1, 1, 1, 1 }

    Returns: 2

  39. 99999

    0

    { 99999 }

    Returns: 99999

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: