CongruenceLock | Topcoder Archive

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

```
10000
```
```
10004
```
```
{1}
```
```
Returns: 4
```
The button labeled with "1" is pushed 4 times.
```
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.
```
11111
```
```
22222
```
```
{4, 6, 2222, 3456}
```
```
Returns: -1
```
```
0
```
```
1
```
```
{3}
```
```
Returns: 66667
```
```
172
```
```
172
```
```
{1, 2, 3, 5, 7}
```
```
Returns: 0
```

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.