Problem Statement
Little Johnny just finished his math homework. He got a nice result: the fraction 16/64.
When his big brother Tommy saw the result, he commented that the task is not finished yet because Johnny didn't reduce the fraction yet. "To reduce it, you must remove what the numerator and denominator have in common."
So, Johnny did that in the only way he knew: he crossed out the "6" both from the numerator and the denominator. Much to everyone's surprise, this left him with the fraction 1/4 that still had the same value.
You are given the
- The denominator of the fraction is D.
- The value of the fraction lies in the open interval (0, 1).
- It is possible to cross out some digits from the denominator and the same collection of digits from the numerator in such a way that you obtain a new fraction with the same value as the fraction you started from.
- You must cross out at least one digit (more precisely, at least one from the numerator and the same number of digits from the denominator).
- You must not cross out all the digits. More precisely, the new fraction's numerator and denominator must still have at least one digit each.
- The numerator and the denominator of the new fraction must not have any leading zeros.
- The crossed-out digits do not have to appear in the same order in the numerator and the denominator, but the values and counts of those digits must exactly match. (E.g., if you cross out 1,1,2 in the numerator, you can cross out 1,2,1 in the denominator but you cannot cross out 2,1,2.)
- After you cross out the digits, the new fraction may still have some digits that appear both in its numerator and in its denominator.
- The new fraction does not have to be reduced (i.e., its numerator and denominator may still have a common factor greater than one).
Return the numerator of your fraction. If there are multiple solutions, you may return any one of them. If there are no solutions, return -1 instead.
Definition
- Class:
- IncorrectCancellation
- Method:
- find
- Parameters:
- int
- Returns:
- int
- Method signature:
- int find(int D)
- (be sure your method is public)
Constraints
- D will be between 1 and 9,999,999, inclusive.
Examples
64
Returns: 16
The example from the problem statement: 16/64 can be "reduced" to 1/4 by crossing out the 6.
98
Returns: 49
We can take 49/98 and cross out the 9 from the numerator and the denominator to get a new fraction 4/8. We see that 49/98 = 4/8, so this is a valid solution. Note that the new fraction does not have to be in its simplest possible form: 4/8 can further be simplified to 1/2 but that does not matter to us in this problem.
470
Returns: 10
A boring example where the reduction is actually a mathematically correct operation. (Crossing out the trailing zero from both the numerator and the denominator corresponds to dividing both by 10.)
1057
Returns: -1
There is no solution for this denominator. Note that 151/1057 is not a valid solution: if you cross out 1, 5 from both the numerator (in either of the two possible ways) and also from the denominator, you will be left with 1/07. This is a fraction with the same value as 151/1057, but we are not allowed to produce leading zeros when crossing out digits. You are also not allowed to cross out the zero from the denominator, as there is no zero to cross out in the numerator.
201
Returns: -1
1285
Returns: -1
Don't forget to check the order: you cannot get 20/25 out of 1028/1285.
15436
Returns: 454
One valid solution is to take the fraction 454 / 15436 and cross out the first two digits of the numerator (4, 5) and the second and third digit of the denominator (5, 4) to produce the fraction 4 / 136.
15425
Returns: 13574
With the numerator 13574 we can "reduce" this fraction by crossing out one digit 1 and one digit 5, as shown below. 13574 / 15425 -> (1)3(5)74 / (1)(5)425 = 374 / 425. Note that in the new fraction the digit 4 still appears both in the numerator and in the denominator. This is explicitly allowed in the problem statement.
6665
Returns: 2666
One valid solution for this fraction is to cross out all the sixes to get 2/5.
1221
Returns: 222
Either cross out a single 2 in each number, or two 2s in each number; producing either the fraction 22/121 or the fraction 2/11. Both of these fractions have the same value as the fraction 222 / 1221 we started from.
1
Returns: -1
2
Returns: -1
3
Returns: -1
10
Returns: -1
19
Returns: -1
20
Returns: 10
9876543
Returns: -1
499731
Returns: -1
499732
Returns: 58792
499733
Returns: 153764
499734
Returns: 249867
499735
Returns: 99947
499736
Returns: 124934
499737
Returns: 71391
499738
Returns: 249869
499739
Returns: -1
499740
Returns: 10
6903000
Returns: 10
2048998
Returns: 1024499
8217327
Returns: -1
8611334
Returns: 4305667
6762466
Returns: -1
5318923
Returns: -1
9597389
Returns: -1
7485351
Returns: -1
7583637
Returns: -1
1686334
Returns: 843167
8021811
Returns: -1
1396946
Returns: 1667
2718923
Returns: -1
1010511
Returns: -1
5425940
Returns: 10
9079114
Returns: 4539557
1153272
Returns: 288318
6294512
Returns: 224804
8175605
Returns: 2237534
4859547
Returns: 315555
4988646
Returns: 2494323
9779007
Returns: 1397001
9622696
Returns: 2405674
7024398
Returns: 3512199
8419237
Returns: -1
5060905
Returns: 1012181
1558079
Returns: -1
7277484
Returns: -1
6929950
Returns: 10
6736361
Returns: -1
593
Returns: -1
594
Returns: 99
595
Returns: 119
604
Returns: 302
616
Returns: 112
17374
Returns: 3577
17336
Returns: 4334
17332
Returns: 4333
17217
Returns: 11478
184
Returns: 138
217
Returns: 124
728
Returns: 224
763
Returns: 436
185
Returns: 148
7
Returns: -1
There can be no valid fraction with the denominator 7. One of many reasons why: it's not possible to cross out some but not all digits of the denominator.
8576568
Returns: 55692
9673600
Returns: 10
1708
Returns: -1