Find Number of Solutions of a Linear Equation of n Variables in C++

In this problem, we are given a linear equation of n variable for the form,

coeff1(var1) + coeff2(var2) + … + coeffn(varn) = value

Find the number of solutions of a linear equation of n variables.

Let’s take an example to understand the problem,

Input

coeff[] = {3, 1}, value = 4

Output

1

Explanation

Equation : 3x + y = 4.
Solution, x = 0, y = 4.

Solution Approach

A simple solution to the problem is by evaluating the value of the equation. Then update the values by calling it recursively. If the value is 0, then solution count is 1. Else recur with value by subtracting coeff values.

Program to illustrate the working of our solution,

Example

 Live Demo

#include<iostream>
using namespace std;
int countSolutionsEq(int coeff[], int start, int end, int value) {
   if (value == 0)
      return 1;
   int coefCount = 0;
   for (int i = start; i <= end; i++)
      if (coeff[i] <= value)
         coefCount += countSolutionsEq(coeff, i, end, value -
         coeff[i]);
   return coefCount;
}
int main() {
   int coeff[] = {3, 5, 1, 2};
   int value = 6;
   int n = sizeof(coeff) / sizeof(coeff[0]);
   cout<<"The number of solutions of the linear equation is "<<countSolutionsEq(coeff, 0, n - 1, value);
   return 0;
}

Output

The number of solutions of the linear equation is 8