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 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.
Among all valid pairs (A, B), find the one for which A * B is minimal. Return the smallest possible value of the product A * B.
Definition
- Class:
- MinProduct
- Method:
- findMin
- Parameters:
- int[], int, int
- Returns:
- long
- Method signature:
- long findMin(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 20.
- blank1, blank2 will be between 1 and 9, inclusive.
- The sum of elements in amount will be at least blank1 + blank2.
Examples
{0,1,1,2,1,1,0,0,0,0}
2
3
Returns: 3042
In this case, we have the numbers {1,2,3,3,4,5}. A must consist of 2 digits, and B must consist of 3 digits. In this case, one optimal solution is to let A = 13 and B = 234. Then, A * B = 3042. We can show that no other way of assigning digits will give a strictly smaller value A * B.
{1,1,1,1,1,1,1,1,1,1}
1
8
Returns: 0
We can let A = 0, B = 98765432.
{1,3,0,0,0,0,0,0,0,0}
2
2
Returns: 11
It is allowed for A or B to have leading zeros.
{0,20,20,20,20,20,20,20,20,20}
9
9
Returns: 12345678987654321
{1,0,0,0,1,0,0,5,3,2}
9
3
Returns: 36556078253
{0,0,0,0,0,0,0,0,0,18}
9
8
Returns: 99999998900000001
{5,1,1,3,2,0,20,4,5,2}
7
9
Returns: 3034806658
{1,1,1,1,3,1,0,1,1,0}
2
1
Returns: 0
{1,0,3,2,2,2,3,2,3,1}
1
3
Returns: 0
{3,3,5,3,2,2,5,3,2,4}
8
5
Returns: 134444563
{2,2,1,6,5,3,2,2,2,5}
4
7
Returns: 15999996
{1,2,2,2,3,1,3,1,2,1}
2
2
Returns: 12
{4,0,2,3,0,0,3,1,2,4}
3
2
Returns: 0
{4,2,2,2,4,4,2,1,4,2}
5
7
Returns: 1223344
{1,2,1,4,1,2,0,0,1,1}
1
3
Returns: 0
{2,3,1,1,1,0,0,1,3,2}
1
5
Returns: 0
{2,2,2,2,4,2,2,2,1,1}
1
6
Returns: 0
{1,1,4,2,1,3,6,2,3,2}
5
6
Returns: 273285465
{2,2,2,3,1,5,1,2,5,1}
3
6
Returns: 122333
{3,2,2,3,1,2,1,1,3,5}
3
8
Returns: 0
{0,1,3,2,2,3,2,3,1,1}
5
1
Returns: 22233
{0,1,2,6,2,6,5,3,1,4}
9
8
Returns: 2877956902042525
{5,2,3,3,0,1,5,1,3,1}
3
3
Returns: 0
{3,3,3,2,3,0,2,4,2,1}
3
4
Returns: 0
{1,3,0,5,6,4,1,2,1,3}
8
1
Returns: 0
{1,1,0,1,1,3,5,2,2,1}
3
6
Returns: 4977924
{7,2,0,4,0,1,2,2,5,1}
7
1
Returns: 0
{0,2,1,3,0,0,4,1,0,2}
5
7
Returns: 16529372514
{2,2,2,2,3,0,1,0,0,3}
8
4
Returns: 148013352
{3,4,1,11,0,3,3,1,4,1}
5
7
Returns: 12356663
{2,1,1,2,1,1,0,2,2,3}
4
2
Returns: 0
{1,0,2,2,3,1,0,0,2,0}
2
7
Returns: 4668890
{1,2,4,0,2,1,1,2,3,2}
9
2
Returns: 122224456
{0,0,2,2,1,1,1,1,2,0}
2
4
Returns: 53935
{2,2,2,4,2,1,0,2,1,1}
4
5
Returns: 147996
{4,1,3,5,2,2,1,5,4,5}
6
8
Returns: 268000008
{3,0,1,4,0,4,1,2,2,1}
8
2
Returns: 0
{1,5,1,2,4,1,1,0,0,0}
8
1
Returns: 0
{2,2,3,3,2,0,3,2,3,3}
4
7
Returns: 14680008
{4,2,2,4,2,0,5,3,1,4}
2
9
Returns: 0
{3,2,4,4,5,2,2,1,2,3}
5
4
Returns: 12222
{2,2,3,4,2,4,7,0,1,1}
4
3
Returns: 1222
{1,1,4,2,4,4,2,3,1,0}
7
5
Returns: 2732725012
{1,4,2,2,2,2,1,1,0,3}
5
2
Returns: 11122
{3,0,4,3,2,0,1,3,2,3}
2
4
Returns: 0
{0,3,1,1,3,1,5,6,3,4}
4
7
Returns: 1411337844
{4,5,3,1,3,5,2,4,1,3}
6
6
Returns: 1223442
{2,0,1,6,4,0,1,1,8,1}
7
7
Returns: 77805962964
{1,2,4,1,2,2,4,3,1,1}
2
7
Returns: 1222234
{3,2,1,1,0,3,3,1,5,3}
8
9
Returns: 1703446001728
{1,7,2,1,2,0,5,1,3,3}
9
8
Returns: 123609077653836
{2,0,1,1,1,2,4,0,2,2}
2
2
Returns: 0
{2,4,1,3,3,3,0,3,2,4}
2
8
Returns: 0
{0,0,2,0,1,4,3,0,4,0}
2
2
Returns: 600
{1,0,1,4,0,0,0,1,2,1}
3
3
Returns: 7659
{1,2,1,2,1,0,4,3,1,5}
9
4
Returns: 16564001271
{1,2,4,3,0,2,1,3,1,2}
3
7
Returns: 14667996
{1, 0, 0, 0, 1, 0, 0, 5, 3, 2 }
9
3
Returns: 36556078253
{8, 0, 0, 0, 0, 0, 0, 0, 0, 20 }
9
9
Returns: 8999999991
{2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }
9
9
Returns: 152415676390796
{0, 1, 1, 2, 1, 1, 0, 0, 0, 0 }
2
3
Returns: 3042
{1, 3, 0, 0, 0, 0, 0, 0, 0, 0 }
2
2
Returns: 11
{2, 1, 0, 0, 0, 1, 1, 1, 1, 1 }
4
4
Returns: 92624
{8, 10, 10, 10, 10, 10, 10, 10, 10, 10 }
5
5
Returns: 0
{0, 2, 2, 2, 2, 2, 2, 2, 2, 2 }
9
9
Returns: 15241578750190521
{8, 1, 0, 0, 0, 0, 0, 0, 0, 20 }
9
9
Returns: 999999999
{0, 10, 10, 10, 10, 10, 10, 10, 10, 10 }
9
9
Returns: 12345925877777284
{0, 2, 0, 0, 0, 0, 0, 0, 0, 20 }
3
1
Returns: 199
{0, 20, 20, 20, 20, 20, 20, 20, 20, 20 }
9
9
Returns: 12345678987654321
{2, 2, 0, 0, 0, 0, 0, 0, 0, 0 }
2
2
Returns: 0
{0, 0, 3, 4, 4, 3, 3, 3, 0, 3 }
9
9
Returns: 52138798846238922
{4, 3, 8, 0, 0, 0, 0, 0, 0, 0 }
5
7
Returns: 1122222