In this Answer, we'll learn how to find the number of positive integral solutions for the equation of form x1 + x2 + ... + xk = n.
This problem is equivalent to finding the number of ways to distribute
If
Let's consider a similar example to understand how to solve this combinatorial problem:
We want to distribute 4 cookies to 3 people such that each person gets at least 1 cookie. Each cookie is represented by a colored circle. 4 circles need 3 gaps which are represented by a red caret. Since there are 3 people, we need 2 bars (|) to fill any of the 3 gaps. This problem is now reduced to finding the binomial coefficient:
In C++ implementation, we use m! = m * (m - 1)! to calculate factorials. We store factorials in unsigned long long
type, so we cannot compute values larger than 20!.
Let's look at the code below:
#include <iostream>using namespace std;//calculates n!, max value of n = 20unsigned long long factorial(int n){unsigned long long fact = 1; //0!= 1, 1!= 1for(int i = 2; i <= n ; i++){fact *= i;}return fact;}int main(){int k = 3;int n = 4;auto ans = (factorial(n - 1)/factorial(k - 1)) / factorial(n-k);cout << ans; //3return 0;}
unsigned long long
, that is, the maximum integer value it can hold is 9 * 1018. This is less than 21! (= 5 * 1019) and greater than 20!, so we can calculate all values where n
< 21.fact *= i
, the variable fact
initially was (i-1)!. After multiplication with i
, fact
becomes i!.n
and k
for equation x1 + x2 + ... + xk = n.The time complexity of the above problem is
Free Resources