Total possible solutions to a linear equation of `k` variables
Given a linear equation of k variables, count the total number of possible solutions to it.
For example,
Input: coeff = {1, 3, 5, 7}, rhs = 8
Output: The total number of solutions is 6
Above input represents the equation a + 3b + 5c + 7d = 8.
( a = 1, b = 0, c = 0, d = 1 )
( a = 0, b = 1, c = 1, d = 0 )
( a = 2, b = 2, c = 0, d = 0 )
( a = 3, b = 0, c = 1, d = 0 )
( a = 5, b = 1, c = 0, d = 0 )
( a = 8, b = 0, c = 0, d = 0 )
Input: coeff = {1, 2, 3}, rhs = 4
Output: The total number of solutions is 4
Above input represents the equation x + 2y + 3z = 4.
( x = 1, y = 0, z = 1 )
( x = 0, y = 2, z = 0 )
( x = 2, y = 1, z = 0 )
( x = 4, y = 0, z = 0 )
Output: The total number of solutions is 6
Above input represents the equation a + 3b + 5c + 7d = 8.
( a = 1, b = 0, c = 0, d = 1 )
( a = 0, b = 1, c = 1, d = 0 )
( a = 2, b = 2, c = 0, d = 0 )
( a = 3, b = 0, c = 1, d = 0 )
( a = 5, b = 1, c = 0, d = 0 )
( a = 8, b = 0, c = 0, d = 0 )
Input: coeff = {1, 2, 3}, rhs = 4
Output: The total number of solutions is 4
Above input represents the equation x + 2y + 3z = 4.
( x = 1, y = 0, z = 1 )
( x = 0, y = 2, z = 0 )
( x = 2, y = 1, z = 0 )
( x = 4, y = 0, z = 0 )
The problem is similar to finding the total number of ways to get the denomination of coins. Here, coefficients of an equation can be considered coins denominations, and the RHS of an equation can be considered the desired change. Let’s begin by recursively defining the problem:
count(coeff, k, rhs) = count(coeff, k, rhs-coeff[k]) + count(coeff, k-1, rhs);
That is, for each coefficient of a variable.
- Include current coefficient
coeff[k]in solution and recur with remaining valuerhs-coeff[k]. - Exclude current coefficient
coeff[k]from the solution and recur for remaining coefficientsk-1.
Finally, return total ways by including or excluding the current coefficient. The recursion’s base case is when the solution is found (i.e., rhs becomes 0), or the solution doesn’t exist (when no coefficients are left, or rhs becomes negative).
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
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 |
#include <iostream> using namespace std; // Function to count the total number of possible solutions to a // linear equation of `k` variables int count(int coeff[], int k, int rhs) { // if rhs become 0, return 1 (solution found) if (rhs == 0) { return 1; } // return 0 (solution does not exist) 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 // recur with remaining value `rhs-coeff[k]` int include = count(coeff, k, rhs - coeff[k]); // Case 2. Exclude current coefficient `coeff[k]` from solution and // recur for remaining coefficients `k-1` int exclude = count(coeff, k - 1, rhs); // return total ways by including or excluding the current coefficient return include + exclude; } int main() { // `k` coefficients of the given equation int coeff[] = { 1, 2, 3 }; int k = sizeof(coeff) / sizeof(coeff[0]); int rhs = 4; cout << "The total number of solutions is " << count(coeff, k - 1, rhs); return 0; } |
Output:
The total number of solutions is 4
Java
|
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 |
class Main { // Function to count the total number of possible solutions to a // linear equation of `k` variables public static int count(int[] coeff, int k, int rhs) { // if rhs become 0, a 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 // recur with remaining value `rhs-coeff[k]` int include = count(coeff, k, rhs - coeff[k]); // Case 2. Exclude current coefficient `coeff[k]` from solution and // recur for remaining coefficients `k-1` int exclude = count(coeff, k - 1, rhs); // return total ways by including or excluding the current coefficient return include + exclude; } public static void main (String[] args) { // `k` coefficients of the given equation int[] coeff = { 1, 2, 3 }; int k = coeff.length; int rhs = 4; System.out.println("The total number of solutions is " + count(coeff, k - 1, rhs)); } } |
Output:
The total number of solutions is 4
Python
|
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 |
# Function to count the total number of possible solutions to a # linear equation of `k` variables def count(coeff, k, rhs): # if rhs become 0, a solution is found if rhs == 0: return 1 # return 0 if rhs becomes negative or no coefficient is left if rhs < 0 or k < 0: return 0 # Case 1. Include current coefficient `coeff[k]` in solution and # recur with remaining value `rhs-coeff[k]` include = count(coeff, k, rhs - coeff[k]) # Case 2. Exclude current coefficient `coeff[k]` from solution and # recur for remaining coefficients `k-1` exclude = count(coeff, k - 1, rhs) # return total ways by including or excluding the current coefficient return include + exclude if __name__ == '__main__': # `k` coefficients of the given equation coeff = [1, 2, 3] k = len(coeff) rhs = 4 print('The total number of solutions is', count(coeff, k - 1, rhs)) |
Output:
The total number of solutions is 4
The time complexity of the above solution is exponential and occupies space in the call stack.
The above solution has an optimal substructure as it can be broken down into smaller subproblems. It also clearly displays overlapping subproblems, and we might end up solving the same subproblem repeatedly. The repeated subproblems can be seen by drawing the recursion tree for higher values of the desired change.
The problems having optimal substructure and overlapping subproblem can be solved using dynamic programming in which subproblem solutions are memoized rather than computed repeatedly. Following is the C++, Java, and Python program that demonstrates it:
C++
|
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 |
#include <iostream> #include <unordered_map> using namespace std; // Function to count the total number of possible solutions to a // linear equation of `k` variables int count(int coeff[], int k, int rhs, auto &lookup) { // if rhs become 0, return 1 (solution found) if (rhs == 0) { return 1; } // return 0 (solution does not exist) 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 = to_string(k) + "|" + to_string(rhs); // if the subproblem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { int include = count(coeff, k, rhs - coeff[k], lookup); // case 1 int exclude = count(coeff, k - 1, rhs, lookup); // case 2 // assign total ways by including or excluding the current coefficient lookup[key] = include + exclude; } // return solution to the current subproblem return lookup[key]; } int main() { // `k` coefficients of the given equation int coeff[] = { 1, 2, 3 }; int k = sizeof(coeff) / sizeof(coeff[0]); int rhs = 4; // create a map to store solutions to a subproblem unordered_map<string, int> lookup; cout << "The total number of solutions is " << count(coeff, k - 1, rhs, lookup); return 0; } |
Output:
The total number of solutions is 4
Java
|
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 |
import java.util.Map; import java.util.HashMap; class Main { // Function to count the total number of possible solutions to a // linear equation of `k` variables public static int count(int[] coeff, int k, int rhs, Map<String, Integer> lookup) { // if rhs become 0, a 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 = k + "|" + rhs; // if the subproblem 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 the current coefficient lookup.put(key, include + exclude); } // return solution to the current subproblem return lookup.get(key); } public static void main (String[] args) { // `k` coefficients of the given equation int[] coeff = { 1, 2, 3 }; int k = coeff.length; int rhs = 4; // create a map to store solutions to a subproblem Map<String, Integer> lookup = new HashMap<>(); System.out.println("The total number of solutions is " + count(coeff, k - 1, rhs, lookup)); } } |
Output:
The total number of solutions is 4
Python
|
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 |
# Function to count the total number of possible solutions to a # linear equation of `k` variables def count(coeff, k, rhs, lookup): # if rhs become 0, a solution is found if rhs == 0: return 1 # return 0 if rhs becomes negative or no coefficient is left if rhs < 0 or k < 0: return 0 # construct a unique key from dynamic elements of the input key = (k, rhs) # if the subproblem is seen for the first time, solve it and # store its result in a dictionary if key not in lookup: include = count(coeff, k, rhs - coeff[k], lookup) # Case 1 exclude = count(coeff, k - 1, rhs, lookup) # Case 2 # return total ways by including or excluding the current coefficient lookup[key] = include + exclude # return solution to the current subproblem return lookup[key] if __name__ == '__main__': # `k` coefficients of the given equation coeff = [1, 2, 3] k = len(coeff) rhs = 4 # create a dictionary to store solutions to a subproblem lookup = {} print('The total number of solutions is', count(coeff, k - 1, rhs, lookup)) |
Output:
The total number of solutions is 4
The time complexity of the above solution is O(k × rhs), and the auxiliary space used by the program is O(k × rhs).
We can even write a bottom-up version of the above memoized solution. The following code shows how to implement this in C, Java, and Python:
C
|
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 |
#include <stdio.h> int count(int coeff[], int k, int rhs) { int T[k + 1][rhs + 1]; for (int i = 0; i <= k; i++) { for (int j = 0; j <= rhs; j++) { if (i == 0) { T[i][j] = 0; } else if (j == 0) { T[i][j] = 1; } else if (coeff[i - 1] > j) { T[i][j] = T[i - 1][j]; } else { T[i][j] = T[i - 1][j] + T[i][j - coeff[i - 1]]; } } } return T[k][rhs]; } int main(void) { int coeff[] = {1, 3, 5, 7}; int rhs = 8; int k = sizeof(coeff) / sizeof(coeff[0]); printf("The total number of solutions is %d", count(coeff, k, rhs)); return 0; } |
Output:
The total number of solutions is 6
Java
|
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 |
class Main { public static int count(int[] coeff, int rhs) { int k = coeff.length; int T[][] = new int[k + 1][rhs + 1]; for (int i = 0; i <= k; i++) { T[i][0] = 1; } for (int i = 1; i <= k; i++) { for (int j = 1; j <= rhs; j++) { if (coeff[i - 1] > j) { T[i][j] = T[i - 1][j]; } else { T[i][j] = T[i - 1][j] + T[i][j - coeff[i - 1]]; } } } return T[k][rhs]; } public static void main(String[] args) { int[] coeff = {1, 3, 5, 7}; int rhs = 8; System.out.println("The total number of solutions is " + count(coeff, rhs)); } } |
Output:
The total number of solutions is 6
Python
|
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 |
def count(coeff, rhs): k = len(coeff) T = [[0] * (rhs + 1) for _ in range(k + 1)] for i in range(k + 1): T[i][0] = 1 for i in range(1, k + 1): for j in range(1, rhs + 1): if coeff[i - 1] > j: T[i][j] = T[i - 1][j] else: T[i][j] = T[i - 1][j] + T[i][j - coeff[i - 1]] return T[k][rhs] if __name__ == '__main__': coeff = [1, 3, 5, 7] rhs = 8 print('The total number of solutions is', count(coeff, rhs)) |
Output:
The total number of solutions is 6
The time and space complexity of the above solution remains the same as the memoized recursive solution. However, the time complexity can be reduced to O(rhs) using the simplified algorithm below:
C
|
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 |
#include <stdio.h> int count(int coeff[], int k, int rhs) { int T[rhs + 1]; for (int i = 0; i <= rhs; i++) { T[i] = 0; } T[0] = 1; for (int i = 0; i < k; i++) { for (int j = coeff[i]; j <= rhs; j++) { T[j] += T[j - coeff[i]]; } } return T[rhs]; } int main(void) { int coeff[] = {1, 3, 5, 7}; int k = sizeof(coeff) / sizeof(coeff[0]); int rhs = 8; printf("The total number of solutions is %d", count(coeff, k, rhs)); return 0; } |
Output:
The total number of solutions is 6
Java
|
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 |
class Main { public static int count(int[] coeff, int rhs) { int k = coeff.length; int T[] = new int[rhs + 1]; T[0] = 1; for (int i = 0; i < k; i++) { for (int j = coeff[i]; j <= rhs; j++) { T[j] += T[j - coeff[i]]; } } return T[rhs]; } public static void main(String[] args) { int[] coeff = {1, 3, 5, 7}; int rhs = 8; System.out.println("The total number of solutions is " + count(coeff, rhs)); } } |
Output:
The total number of solutions is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
def count(coeff, rhs): k = len(coeff) T = [0] * (rhs + 1) T[0] = 1 for i in range(k): for j in range(coeff[i], rhs + 1): T[j] += T[j - coeff[i]] return T[rhs] if __name__ == '__main__': coeff = [1, 3, 5, 7] rhs = 8 print('The total number of solutions is', count(coeff, rhs)) |
Output:
The total number of solutions is 6
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)