Find number of solutions of a linear equation of n variables - GeeksforGeeks
O(n * rhs)
DFS+ cache
countSol(coeff, 0, n-1, rhs);
http://www.techiedelight.com/total-possible-solutions-linear-equation-k-variables/
Given a linear equation of n variables, find number of non-negative integer solutions of it. For example,let the given equation be “x + 2y = 5”, solutions of this equation are “x = 1, y = 2”, “x = 5, y = 0” and “x = 1. It may be assumed that all coefficients in given equation are positive integers.
Example :
Input: coeff[] = {1, 2}, rhs = 5
Output: 3
The equation "x + 2y = 5" has 3 solutions.
(x=3,y=1), (x=1,y=2), (x=5,y=0)
O(n * rhs)
DFS+ cache
The time complexity of above solution is O(k x rhs) and auxiliary space used by the program is O(k x rhs).
public static int count(int coeff[], int k, int rhs,
Map<String, Integer> lookup)
{
// if rhs becomes 0, solution is found
if (rhs == 0)
return 1;
// return 0 if rhs becomes negative or no coefficient is left
if (rhs < 0 || k < 0)
return 0;
// construct a unique map key from dynamic elements of the input
String key = String.valueOf(k) + "|" + String.valueOf(rhs);
// if sub-problem is seen for the first time, solve it and
// store its result in a map
if (lookup.get(key) == null)
{
int include = count(coeff, k, rhs - coeff[k], lookup); // Case 1
int exclude = count(coeff, k - 1, rhs, lookup); // Case 2
// return total ways by including or excluding current coeff
lookup.put(key, include + exclude);
}
// return solution to current sub-problem
return lookup.get(key);
}
// k coefficients of given equation
int[] coeff = { 1, 2, 3 };
final int k = coeff.length;
final int rhs = 4;
// create a map to store solutions of subproblems
Map<String, Integer> lookup = new HashMap<String, Integer>();
System.out.println("Total number of solutions are " +
count(coeff, k - 1, rhs, lookup));
Recursive Version:If rhs = 0
countSol(coeff, 0, rhs, n-1) = 1
Else
countSol(coeff, 0, rhs, n-1) = ∑countSol(coeff, i, rhs-coeff[i], m-1)
where coeff[i]<=rhs and
i varies from 0 to n-1
int countSol(int coeff[], int start, int end, int rhs){ // Base case if (rhs == 0) return 1; int result = 0; // Initialize count of solutions // One by subtract all smaller or equal coefficiants and recur for (int i=start; i<=end; i++) if (coeff[i] <= rhs) result += countSol(coeff, i, end, rhs-coeff[i]); return result;}http://www.techiedelight.com/total-possible-solutions-linear-equation-k-variables/
The problem is similar to finding total number of ways to get the denomination of coins. Here, coefficients of an equation can be considered as coins denominations and RHS of an equation can be considered as desired change. Let us begin by recursively defining the problem –
count(coeff, k, rhs) = count(coeff, k, rhs-coeff[k]) + count(coeff, k-1, rhs);
count(coeff, k, rhs) = count(coeff, k, rhs-coeff[k]) + count(coeff, k-1, rhs);
That is, for each coefficient of a variable
- We include current coefficient coeff[k] in solution and recurse with remaining value (rhs-coeff[k]).
- We exclude current coefficient coeff[k] from solution and recurse for remaining coefficients (k-1).
Finally, we return total ways by including or excluding current coefficient. The base case of the recursion is when solution is found (i.e. rhs becomes 0) or the solution doesn’t exist (when no coefficients are left or rhs becomes negative).
public static int count(int coeff[], int k, int rhs)
{
// if rhs becomes 0, solution is found
if (rhs == 0)
return 1;
// return 0 if rhs becomes negative or no coefficient is left
if (rhs < 0 || k < 0)
return 0;
// Case 1. include current coefficient coeff[k] in solution and
// recurse with remaining value (rhs - coeff[k])
int include = count(coeff, k, rhs - coeff[k]);
// Case 2. exclude current coefficient coeff[k] from solution and
// recurse for remaining coefficients (k - 1)
int exclude = count(coeff, k - 1, rhs);
// return total ways by including or excluding current coefficient
return include + exclude;
}
Read full article from Find number of solutions of a linear equation of n variables - GeeksforGeeks