Problem Statement
You are given an integer s and an integer k. Find k positive integers a1, a2, ..., ak such that their sum is equal to s and their product is the maximal possible. Return their product.
Definition
- Class:
- MaximalProduct
- Method:
- maximalProduct
- Parameters:
- int, int
- Returns:
- long
- Method signature:
- long maximalProduct(int s, int k)
- (be sure your method is public)
Notes
- For all valid inputs, the return value will fit in a long.
Constraints
- k will be between 1 and 20, inclusive.
- s will be between k and 100, inclusive.
Examples
10
3
Returns: 36
The 3 positive integers are 3, 3, 4.
10
1
Returns: 10
10
10
Returns: 1
13
8
Returns: 32
7
2
Returns: 12
1
1
Returns: 1
2
1
Returns: 2
2
2
Returns: 1
3
1
Returns: 3
3
2
Returns: 2
3
3
Returns: 1
4
1
Returns: 4
4
2
Returns: 4
4
3
Returns: 2
4
4
Returns: 1
5
1
Returns: 5
5
2
Returns: 6
5
3
Returns: 4
5
4
Returns: 2
5
5
Returns: 1
6
1
Returns: 6
6
2
Returns: 9
6
3
Returns: 8
6
4
Returns: 4
6
5
Returns: 2
6
6
Returns: 1
7
1
Returns: 7
7
2
Returns: 12
7
3
Returns: 12
7
4
Returns: 8
7
5
Returns: 4
7
6
Returns: 2
7
7
Returns: 1
8
1
Returns: 8
8
2
Returns: 16
8
3
Returns: 18
8
4
Returns: 16
8
5
Returns: 8
8
6
Returns: 4
8
7
Returns: 2
8
8
Returns: 1
9
1
Returns: 9
9
2
Returns: 20
9
3
Returns: 27
9
4
Returns: 24
9
5
Returns: 16
9
6
Returns: 8
9
7
Returns: 4
9
8
Returns: 2
9
9
Returns: 1
10
1
Returns: 10
10
2
Returns: 25
10
3
Returns: 36
10
4
Returns: 36
10
5
Returns: 32
10
6
Returns: 16
10
7
Returns: 8
10
8
Returns: 4
10
9
Returns: 2
10
10
Returns: 1
20
1
Returns: 20
30
1
Returns: 30
40
1
Returns: 40
50
1
Returns: 50
60
1
Returns: 60
70
1
Returns: 70
80
1
Returns: 80
90
1
Returns: 90
100
1
Returns: 100
20
20
Returns: 1
30
20
Returns: 1024
40
20
Returns: 1048576
50
20
Returns: 60466176
60
20
Returns: 3486784401
70
20
Returns: 61917364224
80
20
Returns: 1099511627776
90
20
Returns: 10240000000000
100
20
Returns: 95367431640625
20
2
Returns: 100
20
3
Returns: 294
22
5
Returns: 1600
22
9
Returns: 2592
22
11
Returns: 2048
23
17
Returns: 64
29
14
Returns: 24576
32
6
Returns: 22500
34
8
Returns: 102400
34
18
Returns: 65536
35
5
Returns: 16807
36
3
Returns: 1728
36
7
Returns: 93750
36
13
Returns: 472392
38
5
Returns: 25088
38
18
Returns: 589824
40
5
Returns: 32768
41
3
Returns: 2548
41
14
Returns: 3188646
42
12
Returns: 2985984
47
16
Returns: 28697814
50
16
Returns: 76527504
52
3
Returns: 5202
55
18
Returns: 516560652
57
7
Returns: 2359296
58
8
Returns: 7529536
58
9
Returns: 18670176
60
5
Returns: 248832
60
10
Returns: 60466176
61
13
Returns: 500000000
64
19
Returns: 8707129344
66
17
Returns: 9663676416
68
9
Returns: 78675968
70
4
Returns: 93636
72
6
Returns: 2985984
73
12
Returns: 2539579392
75
7
Returns: 16105100
75
18
Returns: 134217728000
76
7
Returns: 17715610
76
9
Returns: 214990848
76
14
Returns: 18225000000
81
3
Returns: 19683
81
18
Returns: 512000000000
83
11
Returns: 4405854208
86
4
Returns: 213444
89
6
Returns: 10631250
93
5
Returns: 2222316
93
17
Returns: 3280500000000
94
3
Returns: 30752
96
10
Returns: 6561000000
97
15
Returns: 1383235999488
98
9
Returns: 2143588810
98
17
Returns: 8162933760000
98
18
Returns: 16402500000000
99
7
Returns: 112943040
100
5
Returns: 3200000
100
10
Returns: 10000000000
100
19
Returns: 47460937500000
99
10
Returns: 9000000000
100
18
Returns: 23619600000000
100
15
Returns: 2196527536224
96
15
Returns: 1185630856704
12
4
Returns: 81
96
16
Returns: 2821109907456
12
5
Returns: 72
99
20
Returns: 76293945312500
97
20
Returns: 48828125000000
95
10
Returns: 5904900000
96
7
Returns: 90892256
81
19
Returns: 838860800000