The usual longhand scheme for multiplying two numbers A and B is to multiply the last digit of B by A, shift left by one digit, multiply the second-to-last digit of B by A, and so on. This process is illustrated below:
36
x 15
-----
180
+ 36
-----
540
But let's say we didn't multiply in the usual way. Let us define a new method of multiplication called "NC-Multiplication", where the "NC" stands for "No Carry". It is called this because we do not carry when numbers exceed 9, no matter what. To multiply 36 by 15 in this manner, we would do:
3 6
x 1 5
---------
15 30
+ 3 6
---------
3 21 30
and so the result would be {3, 21, 30}.
You will be given a int[] digits, that represents the result of NC-multiplying two numbers together. You wish to factor this result by finding the two numbers that multiplied together to form the result. There may be multiple pairs of numbers that work. If we call the larger number A and the smaller B, then we want the pair such that A - B is minimized. Of this pair, your method should return a long that is equal to A. If no such A and B exist that NC-multiply to digits, your method should return -1. |