### 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

0)

 `10000` `10004` `{1}`
`Returns: 4`
 The button labeled with "1" is pushed 4 times.
1)

 `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.
2)

 `11111` `22222` `{4, 6, 2222, 3456}`
`Returns: -1`
3)

 `0` `1` `{3}`
`Returns: 66667`
4)

 `172` `172` `{1, 2, 3, 5, 7}`
`Returns: 0`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1936

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4656&pm=1936

Wernie

#### Testers:

lbackstrom , brett1479

Search