Statistics

Problem Statement for "NCMultiplication"

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.

Definition

Class:
NCMultiplication
Method:
findFactors
Parameters:
int[]
Returns:
long
Method signature:
long findFactors(int[] digits)
(be sure your method is public)

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

  1. {3,21,30}

    Returns: 36

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

  2. {15,3,6}

    Returns: 512

  3. {4,20,25}

    Returns: 25

    25 NC-Multiplied by 25.

  4. {6,61,124,129,90,27}

    Returns: 6773

  5. {8,14,22,95,125,120,73,9,9}

    Returns: -1

  6. {6,8,32,90,164,178,156,114,66,18}

    Returns: 104993

  7. {1,10,43,104,165,202,217,212,199,126,93,36,36}

    Returns: 1597736

  8. {3,3,3,3,3,3,3,3,3,3,3,3,3,3}

    Returns: 10000001

  9. {4,8,4,8,4,8,4,8,4,8,4,8,4,8}

    Returns: 1010101010101

  10. {1,2,3,4,5,6,7,8,9,1,2,3,4,5}

    Returns: 12345678912345

  11. {1,4,7,10,13,16,13,4,7,10,13,16,12}

    Returns: 12000012

  12. {9,0,0,0,0,0,0,0,0,0,0,0,0,9}

    Returns: 10000000000001

  13. {2,0,0,0,4,0,0,0,8,0,0,0,16}

    Returns: 100000004

  14. {1,2,11,20,46,71,92,170,116,99,72}

    Returns: 116938

  15. {10,58,113,124,130,202,184,76,96,72,15}

    Returns: 598095

  16. {16,24,62,99,137,145,142,124,68,20}

    Returns: 236884

  17. {27,12,109,45,105,53,50,57,16,8,4}

    Returns: 919044

  18. {6,46,85,87,127,143,122,126,70,49,49}

    Returns: 643607

  19. {63,108,138,210,247,224,170,156,109,49,6}

    Returns: 993676

  20. {24,20,38,57,54,77,48,43,21,12,6}

    Returns: 655603

  21. {5,20,59,74,110,157,118,118,81,40,24}

    Returns: 554723

  22. {1,7,3,20,54,40,54,26,43,11,5}

    Returns: 172615

  23. {8,16,28,54,74,94,84,87,70,34,12}

    Returns: 446586

  24. {1,4,7,10,13,16,19,20,17,14,11,8,5,2}

    Returns: 13333332

  25. {1,5,7,10,13,16,19,20,17,14,11,8,5,2}

    Returns: -1

  26. {72,128,159,182,204,210,156,109,74,44,19,3}

    Returns: 8875651

  27. {18,45,61,86,125,157,181,188,148,131,128,77,49}

    Returns: 6751967

  28. {18,34,92,109,58,159,154,102,111,48,60,45,9}

    Returns: 9827263

  29. {10,29,80,131,156,146,144,152,113,90,40,25}

    Returns: 5771655

  30. {5,29,35,59,92,78,125,83,65,81,12,32}

    Returns: 1524714

  31. {72,53,107,53,107,57,146,37,74,18,59,3,24}

    Returns: 9161703

  32. {28,43,73,101,122,134,191,147,162,123,78,58,72}

    Returns: 7277428

  33. {16,56,84,112,146,154,184,177,111,90,48,33,36}

    Returns: 4864214

  34. {63,64,118,129,147,125,215,161,189,133,94,65,72}

    Returns: 9430379

  35. {9,24,30,41,30,42,58,38,24,13,10,6}

    Returns: 3612553

  36. {4,9,43,88,86,137,145,232,131,123,82,91,18}

    Returns: 4977392

  37. {42,104,124,156,164,227,258,165,141,101,86,52,8}

    Returns: 7837784

  38. {27,69,51,52,127,63,69,130,28,34,65,2,18}

    Returns: 9519119

  39. {15,45,57,102,123,156,172,150,128,83,36,25,10}

    Returns: 5047355

  40. {2,8,19,45,60,66,83,69,55,32,23,6}

    Returns: 1145052

  41. {45,27,72,83,68,78,65,44,36,24,10,4,4}

    Returns: 9094402

  42. {42,59,118,105,176,225,235,203,144,150,117,54}

    Returns: 6582896

  43. {10,57,103,87,79,102,114,91,71,45,37,14,6}

    Returns: 5620443

  44. {18,9,42,48,75,75,46,32,21,19,11,3}

    Returns: 6360121

  45. {9,14,59,49,97,125,161,151,132,97,84,60,18}

    Returns: 9596573

  46. {54,99,105,122,183,285,293,255,204,200,193,128,72}

    Returns: 9919779

  47. {1,14,58,114,140,130,137,129,110,65,30,24,6}

    Returns: -1

  48. {12,16,23,23,32,64,61,61,41,40,30,34,20}

    Returns: -1

  49. {36,45,20,80,140,115,161,119,133,145,81,59,7}

    Returns: -1

  50. {15,20,65,81,119,130,133,125,93,93,49,14,14}

    Returns: -1

  51. {21,11,54,71,77,84,104,75,62,42,12}

    Returns: -1

  52. {56,22,66,59,50,118,154,102,67,55,50,69,42}

    Returns: 8205596

  53. {63,126,198,236,236,316,247,209,117,63,81}

    Returns: 999809

  54. {81,162,243,324,405,486,567,486,405,324,243,162,81}

    Returns: 9999999

  55. {72, 103, 116, 70, 76, 157, 149, 108, 62, 52, 33, 14, 8}

    Returns: 95026732

  56. {7, 2, 38, 80, 53, 114, 139, 126, 120, 86, 78, 28, 12, 8}

    Returns: 72376602

  57. {4, 37, 68, 61, 95, 87, 65, 80, 45, 31, 38, 16, 2}

    Returns: 187551451

  58. {6, 12, 42, 97, 119, 138, 164, 168, 132, 111, 84, 42, 24, 9}

    Returns: 11699663

  59. {2, 14, 15, 61, 37, 69, 49, 46, 32, 33, 21, 11, 12, 4}

    Returns: 174632132

  60. {4, 3, 12, 31, 35, 42, 64, 77, 69, 63, 60, 44, 20, 4}

    Returns: 102521562

  61. {8, 7, 3, 38, 70, 64, 95, 95, 55, 53, 34, 13, 12, 4}

    Returns: 10045252

  62. {4, 27, 45, 50, 82, 113, 123, 115, 107, 92, 68, 42, 24, 8}

    Returns: 152657532

  63. {48, 32, 68, 102, 91, 110, 110, 82, 60, 42, 22, 7, 1}

    Returns: 61563541

  64. {2, 23, 78, 96, 70, 33, 51, 46, 34, 22, 14, 4, 4, 4}

    Returns: 299614222

  65. {6, 5, 32, 68, 113, 143, 143, 124, 100, 75, 48, 23, 7, 1}

    Returns: 65864431

  66. {54, 105, 142, 165, 186, 144, 121, 99, 76, 55, 49, 24, 4}

    Returns: 97533052

  67. { 18, 27, 36, 45, 54, 63, 72, 45, 36, 27, 18, 9 }

    Returns: 234567854321

  68. { 1 }

    Returns: 1

  69. { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 10000001

  70. { 8 }

    Returns: 4

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: