Connection Status:
Competition Arena > NCMultiplication

NCMultiplication

SRM 200 · 2004-06-21 · by antimatter

SRM 200 · 2004-06-21 · by antimatter · Advanced Math, Search
Class Name: NCMultiplication
Return Type: long
Method Name: findFactors
Arg Types: (vector<int>)
Problem Statement

Problem Statement

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.

Constraints

  • digits will contain between 1 and 15 elements, inclusive.
  • All elements of digits will be between 0 and 2000, inclusive.
  • At least one element in digits will be nonzero.
  • The number represented by digits will be less than 1014 = 100000000000000.
  • There will be no leading or trailing zeros in digits.
Examples
0)
{3,21,30}
Returns: 36

36 and 15 NC-Multiply together to make {3,21,30}, as seen above.

1)
{15,3,6}
Returns: 512
2)
{4,20,25}
Returns: 25

25 NC-Multiplied by 25.

3)
{6,61,124,129,90,27}
Returns: 6773
4)
{8,14,22,95,125,120,73,9,9}
Returns: -1

Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class NCMultiplication with a public method long long findFactors(vector<int> digits) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous