Problem Statement
You wish to enter a whole number onto your simple four-function calculator. Unfortunately for you, some of the keys are broken. Nonetheless, rather than buy a new calculator, you enjoy the challenge presented before you.
Your calculator is a very primitive one, and can only display positive numbers with up to three digits. Initially, your display does not show anything, until you press a number key. Any time an operation exceeds the number 999, it causes an error, and you cannot continue.
You are given
When you perform a division, your calculator performs an integer division, dropping any remainder. Thus, pressing "23/7=" yields 3, and "3/8" yields 0. Pressing the equals key completes any calculation, and any subsequent key presses after pressing equals discards the current display, and starts a new calculation.
You are to return an
Definition
- Class:
- BrokenCalculator
- Method:
- fewestKeys
- Parameters:
- int[], String, int
- Returns:
- int
- Method signature:
- int fewestKeys(int[] keys, String operators, int target)
- (be sure your method is public)
Notes
- Like most simple four function calculators, pressing any operator has the effect of performing an "equals" on anything entered so far, and operations are performed in exactly the order entered. Thus, 2 + 2 * 3 = evaluates to 12 (instead of 8, as with typical order of operations).
Constraints
- keys will contain between 1 and 10 elements, inclusive.
- Each element of keys will be between 0 and 9, inclusive.
- No two elements of keys will be the same.
- operators will contain between 1 and 4 characters, inclusive.
- Each character of operators will be '+', '-', '*', or '/'.
- No two characters of operators will be the same.
- target will be between 1 and 999, inclusive.
Examples
{0, 1, 2, 3}
"+"
5
Returns: 4
Here, if we type "2 + 3 =", our calculator will display "5", thus, we need four key presses.
{0}
"+-*/"
5
Returns: -1
With only a "0" to press, no operations will get us to the number 5.
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
"/-+*"
124
Returns: 3
With all of the keys available to us, we need only type in the number we want. Notice that the order in which we define the operators doesn't matter.
{1, 2, 4, 8}
"+-*/"
875
Returns: 8
{5,6,7,9}
"/"
476
Returns: -1
{1,3,4,5,6,7,9}
"+/"
13
Returns: 2
{3,4,5,7,8,9}
"+-*"
887
Returns: 3
{3,5,6,7,9}
"/"
363
Returns: 3
{7,8,9}
"+*"
825
Returns: 10
{1,2,4,6,9}
"-*"
935
Returns: 6
{3,4,5,6,7,8}
"-/"
744
Returns: 3
{1,5,6,7}
"-*/"
375
Returns: 5
{4,7}
"-/"
79
Returns: 12
{3,4,5,7,9}
"+-*/"
801
Returns: 6
{1,9}
"-*"
443
Returns: 18
{1,2,3,6}
"-*"
450
Returns: 8
{3,4,5,6,9}
"+/"
586
Returns: 7
{9}
"+-"
647
Returns: -1
{2,3,7,8,9}
"+"
534
Returns: 8
{6}
"+/"
137
Returns: 17
{9}
"+-/"
493
Returns: 27
{2,3,4,6,8}
"+-*/"
842
Returns: 3
{3,4,5,7,9}
"*"
640
Returns: -1
{8}
"+-/"
75
Returns: 14
{7 }
"/-"
553
Returns: 30
{1, 2, 4, 8 }
"+-*/"
875
Returns: 8
{1 }
"*"
2
Returns: -1
{9, 2 }
"/+"
166
Returns: 11
{6, 2 }
"/+"
335
Returns: 8
{1 }
"*"
121
Returns: 6
{3 }
"+"
30
Returns: 20
{6 }
"*"
36
Returns: 4
{0, 5, 7 }
"+-*/"
507
Returns: 3
{9, 8 }
"*/"
820
Returns: -1
{0, 1, 2, 3, 7 }
"-/*"
4
Returns: 4
{1 }
"+"
997
Returns: 79
{1, 0 }
"+"
101
Returns: 3
{0, 1, 2, 3, 7 }
"-/*"
6
Returns: 4
{3 }
"/+*"
10
Returns: 7
{1 }
"+"
999
Returns: 36
{8, 2 }
"/"
4
Returns: 4
{1, 2, 0 }
"+-*/"
2
Returns: 1
{0, 1, 2, 3, 4, 5, 6, 8, 9 }
"*"
997
Returns: -1
{4, 5 }
"+*"
81
Returns: 9
{1, 3, 4 }
"+-*/"
888
Returns: 8
{1, 0, 3 }
"/"
103
Returns: 3
{1 }
"*+"
144
Returns: 12
{9, 0, 1, 2, 3, 4, 5, 6, 7 }
"+-*/"
899
Returns: 6
{0, 1, 3, 7 }
"+*/"
1
Returns: 1