Problem Statement
A * x + B * y + C * z = W
where x, y and z are integers greater than or equal to 0. Return the minimal possible sum x + y + z, or -1 if a solution does not exist.Definition
- Class:
- SolvingEquation
- Method:
- solve
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int solve(int A, int B, int C, int W)
- (be sure your method is public)
Constraints
- A, B, C and W will each be between 1 and 100, inclusive.
Examples
1
2
3
5
Returns: 2
The solution that minimizes x + y + z is x = 0, y = 1 and z = 1. 1*0 + 2*1 + 3*1 = 5. The return value is x + y + z = 0 + 1 + 1 = 2.
1
2
3
10
Returns: 4
The best solution here is x = 1, y = 0 and z = 3.
1
11
7
30
Returns: 4
3
3
5
7
Returns: -1
There is no solution for the equation 3*x + 3*y + 5*z = 7.
4
66
24
14
Returns: -1
6
50
4
81
Returns: -1
8
85
24
82
Returns: -1
9
35
27
21
Returns: -1
10
33
72
99
Returns: 3
11
28
87
69
Returns: -1
21
17
29
41
Returns: -1
23
60
1
26
Returns: 4
24
41
50
66
Returns: -1
28
43
22
40
Returns: -1
30
66
63
95
Returns: -1
30
83
86
38
Returns: -1
31
58
76
25
Returns: -1
33
36
49
3
Returns: -1
34
46
37
73
Returns: -1
38
87
2
28
Returns: 14
41
31
66
82
Returns: 2
42
57
18
29
Returns: -1
46
81
57
75
Returns: -1
47
27
58
21
Returns: -1
48
70
12
52
Returns: -1
49
42
10
42
Returns: 1
49
67
57
40
Returns: -1
51
5
66
61
Returns: 3
51
81
69
8
Returns: -1
52
86
45
44
Returns: -1
56
75
85
71
Returns: -1
56
93
29
27
Returns: -1
56
99
4
94
Returns: -1
59
8
21
91
Returns: 5
62
44
14
30
Returns: -1
62
95
50
21
Returns: -1
64
22
45
84
Returns: -1
64
25
56
40
Returns: -1
64
70
74
34
Returns: -1
65
70
35
72
Returns: -1
67
58
13
59
Returns: -1
67
69
43
9
Returns: -1
68
5
44
22
Returns: -1
71
94
18
6
Returns: -1
73
96
30
63
Returns: -1
75
40
61
35
Returns: -1
76
16
40
75
Returns: -1
77
98
66
94
Returns: -1
80
79
14
88
Returns: -1
83
54
84
5
Returns: -1
84
21
81
27
Returns: -1
87
31
54
68
Returns: -1
87
91
58
32
Returns: -1
90
13
81
7
Returns: -1
94
42
35
50
Returns: -1
96
9
43
13
Returns: -1
97
44
49
81
Returns: -1
99
3
62
36
Returns: 12
100
33
46
39
Returns: -1
100
37
82
18
Returns: -1
1
1
1
100
Returns: 100
100
100
100
100
Returns: 1
1
10
20
99
Returns: 14
1
2
5
99
Returns: 21
2
7
13
35
Returns: 4
2
3
5
96
Returns: 20
100
100
1
1
Returns: 1
100
1
100
1
Returns: 1
1
100
100
1
Returns: 1
96
4
1
100
Returns: 2
1
1
1
1
Returns: 1
34
2
1
99
Returns: 18
100
1
1
100
Returns: 1
10
10
1
100
Returns: 10
2
1
1
100
Returns: 50
100
100
1
100
Returns: 1
6
3
4
10
Returns: 2
5
1
2
10
Returns: 2
5
1
2
5
Returns: 1
6
5
1
10
Returns: 2
7
2
9
8
Returns: 4
100
100
1
99
Returns: 99
7
2
9
10
Returns: 5
2
3
9
100
Returns: 14