Problem Statement
You are given an array amount with exactly 10 elements, where the i-th element denotes the number of copies of the digit i you have.
You would like to construct construct two nonnegative integers A and B. The base-10 representation of A must have exactly blank1 digits. The base-10 representation of B must have exactly blank2 digits. It is allowed for A and B to contain leading zeros. In addition, the total number of appearances of digit i in the numbers A and B must be at most amount[i]. It's guaranteed that the sum of amount is at least blank1 + blank2.
For every distinct ordered pair (A,B) which you can construct, compute the product A * B. Return the sum of all these products, modulo 10^9+7.
Definition
- Class:
- SumProduct
- Method:
- findSum
- Parameters:
- int[], int, int
- Returns:
- int
- Method signature:
- int findSum(int[] amount, int blank1, int blank2)
- (be sure your method is public)
Constraints
- amount will have exactly 10 elements.
- Each element of amount will be between 0 and 100.
- blank1, blank2 will be between 1 and 100, inclusive.
- The sum of elements in amount will be at least blank1 + blank2.
Examples
{0,2,1,1,0,0,0,0,0,0}
2
2
Returns: 4114
The different choices for (A,B) are (11, 23), (11, 32), (12, 13), (12, 31), (13, 12), (13, 21), (21, 13), (21, 31), (31, 12), (31, 21), (23, 11), (32, 11). The sum of all products A * B is 4114.
{1,6,0,0,0,0,0,0,0,0}
1
2
Returns: 22
Remember that the numbers are allowed to have leading zeros.
{1,2,3,4,5,6,7,8,9,10}
15
3
Returns: 340242570
Don't forget about the mod.
{3,14,15,92,65,35,89,79,32,38}
46
26
Returns: 417461139
{100,100,100,100,100,100,100,100,100,100}
100
100
Returns: 372980218
{2,5,7,4,6,3,9,2,4,4}
8
9
Returns: 689334862
{48,46,44,38,44,34,41,34,42,46}
70
90
Returns: 101929417
{15,28,20,18,23,29,27,19,23,22}
54
21
Returns: 200883709
{36,25,42,42,31,34,38,28,31,45}
26
67
Returns: 560958906
{15,18,11,18,17,17,11,20,11,20}
3
47
Returns: 39423718
{28,33,24,18,19,22,28,27,17,18}
31
43
Returns: 29128336
{54,50,47,61,41,55,55,52,38,53}
88
86
Returns: 581337330
{49,53,51,56,45,52,56,65,50,45}
94
71
Returns: 361770858
{13,17,20,23,25,20,15,12,14,25}
25
42
Returns: 745589661
{26,19,23,36,28,22,21,17,28,29}
100
89
Returns: 971350630
{45,45,51,57,57,53,44,55,37,54}
81
21
Returns: 714105529
{28,29,37,31,24,33,23,34,23,36}
4
44
Returns: 328299740
{28,20,21,30,27,21,26,23,27,32}
1
96
Returns: 516042398
{39,51,46,33,45,37,37,44,42,45}
75
35
Returns: 322680934
{43,54,47,55,49,56,46,44,51,61}
83
91
Returns: 564525579
{23,30,27,29,35,29,33,30,36,31}
14
45
Returns: 569403035
{31,32,23,32,31,29,39,29,30,24}
21
20
Returns: 905570094
{44,61,56,57,51,53,67,67,71,58}
39
59
Returns: 324338796
{8,9,14,8,14,11,16,7,11,13}
13
83
Returns: 609563607
{63,47,56,44,66,58,66,49,48,67}
96
45
Returns: 450165722
{54,56,47,52,54,42,58,56,52,65}
91
55
Returns: 345138134
{31,22,17,22,25,20,20,18,21,22}
67
13
Returns: 257768498
{36,38,28,39,23,29,22,30,31,28}
49
21
Returns: 518160048
{31,30,30,31,31,24,23,27,28,22}
21
61
Returns: 180717768
{35,30,33,23,26,35,36,34,34,33}
96
99
Returns: 504149586
{40,25,27,26,21,29,30,41,20,28}
80
42
Returns: 34106955
{28,33,39,25,27,31,31,39,24,35}
71
48
Returns: 370913324
{33,27,32,27,28,33,24,37,32,38}
27
10
Returns: 263109739
{42,27,34,32,24,36,32,31,34,33}
70
31
Returns: 365693379
{26,28,26,25,40,38,34,38,25,29}
12
9
Returns: 686098000
{61,54,59,55,51,61,66,57,56,60}
15
76
Returns: 505554842
{12,25,19,24,23,21,20,22,18,21}
23
67
Returns: 701663028
{18,7,13,13,14,11,12,12,15,14}
65
13
Returns: 444332791
{58,55,43,38,54,60,41,55,50,67}
23
34
Returns: 419776940
{61,43,41,49,57,42,49,51,51,39}
71
74
Returns: 310694639
{37,47,44,46,39,53,34,38,39,47}
51
44
Returns: 782418600
{31,22,27,18,23,18,36,23,29,25}
38
65
Returns: 650533726
{67,50,58,66,56,60,58,52,72,72}
92
81
Returns: 741194690
{56,57,60,46,51,49,61,47,46,55}
40
26
Returns: 904115011
{30,31,45,38,43,33,42,33,32,57}
12
5
Returns: 967386089
{46,39,38,36,53,51,46,57,45,44}
61
81
Returns: 839714388
{38,45,38,37,46,51,38,37,51,41}
66
13
Returns: 471586881
{39,50,39,48,47,53,42,42,42,32}
33
96
Returns: 554144120
{18,28,35,25,38,27,26,32,28,34}
43
27
Returns: 188577213
{48,41,46,40,30,42,32,43,45,43}
34
38
Returns: 418004584
{19,25,23,24,31,22,27,24,23,14}
59
8
Returns: 369043963
{21,18,21,22,20,17,26,17,16,17}
47
11
Returns: 255650536
{46,25,55,37,29,34,51,47,33,44}
38
83
Returns: 377720332
{10,9,7,8,8,9,10,10,9,5}
53
29
Returns: 121254400
{26,27,37,19,21,26,22,20,13,25}
22
59
Returns: 737488339
{13,17,11,18,15,9,17,15,19,10}
61
63
Returns: 863078662
{45,50,48,35,48,44,54,52,46,48}
64
7
Returns: 739139811
{13,15,13,21,12,17,17,17,18,21}
65
66
Returns: 400828873
{3,7,3,6,6,8,7,9,3,9}
4
25
Returns: 788431185
{39,43,30,31,35,28,37,37,39,28}
47
38
Returns: 712202010
{42,30,35,30,46,32,31,32,39,46}
94
60
Returns: 628725956
{52,59,61,52,53,51,52,56,58,58}
86
73
Returns: 139285225
{13,14,15,15,19,16,16,11,18,19}
20
90
Returns: 710977810
{41,46,50,55,47,49,41,44,54,41}
83
70
Returns: 891615458
{10,10,6,6,10,7,9,12,6,6}
23
57
Returns: 317751796
{37,39,28,33,44,32,53,48,41,34}
5
72
Returns: 729666301
{12,6,11,10,11,4,7,5,10,3}
21
43
Returns: 175250007
{40,39,51,49,47,28,49,40,56,60}
51
73
Returns: 231577417
{19,17,23,26,19,22,13,25,14,22}
89
68
Returns: 278195767
{25,20,29,34,29,29,30,21,26,33}
92
47
Returns: 880790386
{53,58,45,37,31,50,52,39,41,47}
84
89
Returns: 681654866
{50,34,39,44,49,55,55,47,47,36}
23
68
Returns: 498570188
{7,9,6,5,9,9,5,8,6,8}
36
1
Returns: 638728125
{38,43,50,55,45,58,59,55,52,48}
68
49
Returns: 624960793
{59,53,54,80,51,65,59,64,57,54}
84
50
Returns: 882444436
{38,42,31,31,45,28,33,42,40,31}
47
30
Returns: 479236644
{15,15,18,12,14,18,13,13,14,16}
31
49
Returns: 510345232
{28,14,19,15,20,23,27,18,26,20}
95
48
Returns: 237356076
{14,20,26,18,24,22,21,20,19,15}
53
32
Returns: 537469816
{64,50,42,60,57,51,43,61,56,59}
67
30
Returns: 681092920
{43,48,47,51,41,39,46,48,53,46}
38
77
Returns: 288866932
{14,6,14,8,14,9,13,13,13,19}
66
7
Returns: 676698653
{28,23,19,30,20,28,28,27,28,23}
65
79
Returns: 21854505
{28,18,31,27,25,25,24,28,33,23}
6
28
Returns: 447107920
{32,34,30,39,31,26,40,32,35,28}
54
94
Returns: 157002853
{43,47,52,39,47,39,43,32,41,39}
64
95
Returns: 89908509
{23,18,12,19,15,9,16,11,15,16}
97
6
Returns: 192519090
{40,41,50,34,48,28,40,27,36,39}
9
52
Returns: 48994176
{24,27,21,25,23,28,18,22,17,18}
95
50
Returns: 28059530
{13,12,6,26,16,18,19,12,16,15}
46
93
Returns: 203987609
{16,21,12,10,15,14,20,17,18,13}
26
65
Returns: 611807949
{61,52,44,55,54,55,62,56,53,55}
46
43
Returns: 378410349
{36,34,34,29,25,30,30,23,25,30}
19
32
Returns: 223798668
{12,9,11,17,13,29,21,16,13,16}
45
78
Returns: 920946887
{48,37,43,46,69,45,48,55,44,58}
28
79
Returns: 532163961
{27,27,26,37,27,32,24,22,36,25}
42
82
Returns: 122668146
{15,14,19,19,23,17,17,19,12,24}
55
68
Returns: 263295792
{66,43,53,51,48,59,59,45,50,43}
30
93
Returns: 28704605
{31,30,40,36,41,23,26,31,42,33}
7
37
Returns: 56963212
{48,64,58,37,53,53,49,42,51,60}
99
75
Returns: 632107849
{61,46,59,54,53,47,56,55,60,47}
50
46
Returns: 844777671
{13,14,14,13,29,9,23,12,19,14}
18
76
Returns: 79537178
{61,58,64,51,45,59,45,64,65,49}
96
87
Returns: 772102497
{34,41,35,34,34,39,38,44,31,44}
30
89
Returns: 438600426
{42,52,37,35,43,52,43,40,58,38}
8
26
Returns: 541425364
{100, 100, 99, 100, 100, 100, 100, 100, 100, 100 }
100
100
Returns: 693400840
{100, 100, 100, 100, 100, 100, 100, 100, 100, 100 }
100
100
Returns: 372980218
{91, 67, 84, 50, 69, 74, 78, 58, 62, 64 }
100
100
Returns: 561018492