forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathLinearDiophantineEquationsSolver.java
More file actions
306 lines (278 loc) · 9.13 KB
/
LinearDiophantineEquationsSolver.java
File metadata and controls
306 lines (278 loc) · 9.13 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
package com.thealgorithms.maths;
import java.util.Objects;
/**
* A solver for linear Diophantine equations of the form ax + by = c.
* <p>
* A linear Diophantine equation is an equation in which only integer solutions
* are allowed.
* This solver uses the Extended Euclidean Algorithm to find integer solutions
* (x, y)
* for equations of the form ax + by = c, where a, b, and c are integers.
* </p>
* <p>
* The equation has solutions if and only if gcd(a, b) divides c.
* If solutions exist, this solver finds one particular solution.
* </p>
*
* @see <a href="https://en.wikipedia.org/wiki/Diophantine_equation">Diophantine
* Equation</a>
* @see <a href=
* "https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm">Extended
* Euclidean Algorithm</a>
*/
public final class LinearDiophantineEquationsSolver {
private LinearDiophantineEquationsSolver() {
}
/**
* Demonstrates the solver with a sample equation: 3x + 4y = 7.
*
* @param args command line arguments (not used)
*/
public static void main(String[] args) {
// 3x + 4y = 7
final var toSolve = new Equation(3, 4, 7);
System.out.println(findAnySolution(toSolve));
}
/**
* Finds any integer solution to the linear Diophantine equation ax + by = c.
* <p>
* The method returns one of three types of solutions:
* <ul>
* <li>A specific solution (x, y) if solutions exist</li>
* <li>{@link Solution#NO_SOLUTION} if no integer solutions exist</li>
* <li>{@link Solution#INFINITE_SOLUTIONS} if the equation is 0x + 0y = 0</li>
* </ul>
* </p>
*
* @param equation the linear Diophantine equation to solve
* @return a Solution object containing the result
* @throws NullPointerException if equation is null
*/
public static Solution findAnySolution(final Equation equation) {
if (equation.a() == 0 && equation.b() == 0 && equation.c() == 0) {
return Solution.INFINITE_SOLUTIONS;
}
if (equation.a() == 0 && equation.b() == 0) {
return Solution.NO_SOLUTION;
}
if (equation.a() == 0) {
if (equation.c() % equation.b() == 0) {
return new Solution(0, equation.c() / equation.b());
} else {
return Solution.NO_SOLUTION;
}
}
if (equation.b() == 0) {
if (equation.c() % equation.a() == 0) {
return new Solution(equation.c() / equation.a(), 0);
} else {
return Solution.NO_SOLUTION;
}
}
final var stub = new GcdSolutionWrapper(0, new Solution(0, 0));
final var gcdSolution = gcd(equation.a(), equation.b(), stub);
if (equation.c() % gcdSolution.getGcd() != 0) {
return Solution.NO_SOLUTION;
}
final var toReturn = new Solution(0, 0);
var xToSet = stub.getSolution().getX() * (equation.c() / stub.getGcd());
var yToSet = stub.getSolution().getY() * (equation.c() / stub.getGcd());
toReturn.setX(xToSet);
toReturn.setY(yToSet);
return toReturn;
}
/**
* Computes the GCD of two integers using the Extended Euclidean Algorithm.
* <p>
* This method also finds coefficients x and y such that ax + by = gcd(a, b).
* The coefficients are stored in the 'previous' wrapper object.
* </p>
*
* @param a the first integer
* @param b the second integer
* @param previous a wrapper to store the solution coefficients
* @return a GcdSolutionWrapper containing the GCD and coefficients
*/
private static GcdSolutionWrapper gcd(final int a, final int b, final GcdSolutionWrapper previous) {
if (b == 0) {
return new GcdSolutionWrapper(a, new Solution(1, 0));
}
// stub wrapper becomes the `previous` of the next recursive call
final var stubWrapper = new GcdSolutionWrapper(0, new Solution(0, 0));
final var next = gcd(b, a % b, stubWrapper);
previous.getSolution().setX(next.getSolution().getY());
previous.getSolution().setY(next.getSolution().getX() - (a / b) * (next.getSolution().getY()));
previous.setGcd(next.getGcd());
return new GcdSolutionWrapper(next.getGcd(), previous.getSolution());
}
/**
* Represents a solution (x, y) to a linear Diophantine equation.
* <p>
* Special instances:
* <ul>
* <li>{@link #NO_SOLUTION} - indicates no integer solutions exist</li>
* <li>{@link #INFINITE_SOLUTIONS} - indicates infinitely many solutions
* exist</li>
* </ul>
* </p>
*/
public static final class Solution {
/**
* Singleton instance representing the case where no solution exists.
*/
public static final Solution NO_SOLUTION = new Solution(Integer.MAX_VALUE, Integer.MAX_VALUE);
/**
* Singleton instance representing the case where infinite solutions exist.
*/
public static final Solution INFINITE_SOLUTIONS = new Solution(Integer.MIN_VALUE, Integer.MIN_VALUE);
private int x;
private int y;
/**
* Constructs a solution with the given x and y values.
*
* @param x the x coordinate of the solution
* @param y the y coordinate of the solution
*/
public Solution(int x, int y) {
this.x = x;
this.y = y;
}
/**
* Gets the x value of this solution.
*
* @return the x value
*/
public int getX() {
return x;
}
/**
* Gets the y value of this solution.
*
* @return the y value
*/
public int getY() {
return y;
}
/**
* Sets the x value of this solution.
*
* @param x the new x value
*/
public void setX(int x) {
this.x = x;
}
/**
* Sets the y value of this solution.
*
* @param y the new y value
*/
public void setY(int y) {
this.y = y;
}
@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (obj == null || obj.getClass() != this.getClass()) {
return false;
}
var that = (Solution) obj;
return this.x == that.x && this.y == that.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
@Override
public String toString() {
return "Solution["
+ "x=" + x + ", "
+ "y=" + y + ']';
}
}
/**
* Represents a linear Diophantine equation of the form ax + by = c.
*
* @param a the coefficient of x
* @param b the coefficient of y
* @param c the constant term
*/
public record Equation(int a, int b, int c) {
}
/**
* A wrapper class that holds both the GCD and the solution coefficients
* from the Extended Euclidean Algorithm.
* <p>
* This class is used internally to pass results between recursive calls
* of the GCD computation.
* </p>
*/
public static final class GcdSolutionWrapper {
private int gcd;
private Solution solution;
/**
* Constructs a GcdSolutionWrapper with the given GCD and solution.
*
* @param gcd the greatest common divisor
* @param solution the solution coefficients
*/
public GcdSolutionWrapper(int gcd, Solution solution) {
this.gcd = gcd;
this.solution = solution;
}
@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (obj == null || obj.getClass() != this.getClass()) {
return false;
}
var that = (GcdSolutionWrapper) obj;
return (this.gcd == that.gcd && Objects.equals(this.solution, that.solution));
}
/**
* Gets the GCD value.
*
* @return the GCD
*/
public int getGcd() {
return gcd;
}
/**
* Sets the GCD value.
*
* @param gcd the new GCD value
*/
public void setGcd(int gcd) {
this.gcd = gcd;
}
/**
* Gets the solution coefficients.
*
* @return the solution
*/
public Solution getSolution() {
return solution;
}
/**
* Sets the solution coefficients.
*
* @param solution the new solution
*/
public void setSolution(Solution solution) {
this.solution = solution;
}
@Override
public int hashCode() {
return Objects.hash(gcd, solution);
}
@Override
public String toString() {
return ("GcdSolutionWrapper["
+ "gcd=" + gcd + ", "
+ "solution=" + solution + ']');
}
}
}