TopCoder problem "BrokenButtons" used in SRM 358 (Division I Level One , Division II Level Two)



Problem Statement

    You want to see some page on the teletext (information service on TV where we refer to pages of information by numbers). Unfortunately, some of the digit buttons on the remote control are broken. But you have an idea! If you can't enter the number of the page you want to see, you could enter some other number and with the buttons '+' and '-' (which are not broken) navigate to the desired page. Button '+' increases the number by 1 and button '-' decreases the number by 1. You are initially at page 100. To go to a different page, you may enter the page number using the digit buttons that aren't broken. Then, press the '+' and '-' buttons to navigate to your desired page.



You will be given an int page, the page you want to see, and a int[] broken, the list of broken digit buttons. Return the minimum number of button presses required to navigate to the page.



 

Definition

    
Class:BrokenButtons
Method:minPresses
Parameters:int, int[]
Returns:int
Method signature:int minPresses(int page, int[] broken)
(be sure your method is public)
    
 

Constraints

-page will be between 0 and 500,000, inclusive.
-broken will contain between 0 and 10 elements, inclusive.
-Each element of broken will be between 0 and 9, inclusive.
-All elements of broken will be distinct.
 

Examples

0)
    
5457
{ 6, 7, 8 }
Returns: 6
You can go to page 5457 either by pressing "5455++" or "5459--".
1)
    
100
{ 1, 0, 5 }
Returns: 0
If you don't enter anything you'll get page 100.
2)
    
14124
{ }
Returns: 5
3)
    
1
{1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 2
We can enter page 0.
4)
    
80000
{ 8, 9 }
Returns: 2228

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10768&pm=7716

Writer:

icanadi

Testers:

PabloGilberto , brett1479 , Olexiy , Andrew_Lazarev

Problem categories:

Brute Force, Simple Math