Given two integers n and r, compute the value of nCr. In simple words, the task is to find how many different ways r items can be chosen from n items when the order of picking does not matter.
If r > n, the answer should be 0 because it is not possible to choose more items than the total available items.
Example 1
Input: n = 5, r = 2
Output: 10
Explanation: The value of 5C2 is 5! / (2! * 3!) = 10.
Example 2
Input: n = 6, r = 3
Output: 20
Explanation: The value of 6C3 is 6! / (3! * 3!) = 20.
Brute Force Approach
The most direct thought is to use the standard combination formula: nCr = n! / (r! * (n - r)!)
Once that formula is known, the problem becomes: first compute three factorials, then divide them in the correct order.
This approach is a good starting point because it matches the exact math definition of nCr.
A beginner can immediately connect the formula on paper with the code in the program.
The important limitation is that factorial values grow very fast.
Even when the final answer fits in a normal integer type, intermediate factorials like 20! or 25! can already become very large.
So this approach is mainly useful for understanding the formula and for small inputs.
Algorithm
First, check if
r > n. This is done because choosing more items than available items is impossible, so the answer must be0.Compute
n!so the numerator of the combination formula is ready.Compute
r!because the selectedritems can be arranged inr!ways, and those repeated orderings must be removed.Compute
(n - r)!because the unselected items also contribute to the formula.Divide
n!byr! * (n - r)!to get the final number of valid combinations.
Dry Run
Compute NcR Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the factorial of a number using iterative multiplication. */ long long factorial(int value) { // Keep the factorial result growing step by step. long long fact = 1; /* Multiply every number from 2 to value because each one belongs to value!. */ for (int i = 2; i <= value; i++) { fact *= i; } return fact; } /* Computes nCr by directly using the factorial formula. */ long long computeNcrBruteForce(int n, int r) { /* If more items are chosen than available, no valid selection can be formed. */ if (r > n) { return 0; } /* Store n! for the numerator part of the formula. */ long long numerator = factorial(n); /* Store r! to remove repeated orderings of chosen items. */ long long rFactorial = factorial(r); /* Store (n - r)! for the remaining unchosen items in the formula. */ long long remainingFactorial = factorial(n - r); return numerator / (rFactorial * remainingFactorial); }};// Driver code startsint main() { int n = 5; int r = 2; Solution obj; cout << obj.computeNcrBruteForce(n, r) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because factorial values are computed with loops up to n.
Space Complexity: O(1), because constant extra space is used.
Optimal Approach
The direct factorial formula is correct, but it creates very large intermediate values. A better observation is that the result can be built step by step: nCr = (n * (n - 1) * (n - 2) * ... * (n - r + 1)) / (1 * 2 * 3 * ... * r)
This version avoids computing three full factorials. There is one more very useful pattern: nCr = nC(n - r)
This means choosing r items is the same as leaving behind n - r items. So instead of looping r times, the loop can run only min(r, n - r) times. That small observation makes the method faster and cleaner.
This is usually the best exact-value approach for a single nCr query when inputs are not asking for modulo arithmetic.
Algorithm
First, check if
r > n. This is needed because such a selection is impossible, so the answer is immediately0.Replace
rwithmin(r, n - r)to use the smaller side of the combination formula and reduce the number of iterations.Keep a variable
answeras1to build the result gradually.For each step from
1tor, multiplyanswerby the next numerator valuen - r + i. This adds one needed factor from the top part of the formula.Then divide
answerbyi. This removes the matching denominator factor at the same step, so the value stays controlled instead of growing like full factorials.After the loop finishes, return
answerbecause all required numerator and denominator factors have been processed.
Dry Run
Compute NcR Brute Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Computes nCr by building the answer one fraction step at a time. */ long long computeNcrBetter(int n, int r) { /* If more items are chosen than available, the answer must be 0. */ if (r > n) { return 0; } /* Use the smaller side because nCr and nC(n - r) are equal. */ if (r > n - r) { r = n - r; } /* Start with 1 so the product can grow safely from a neutral value. */ long long answer = 1; /* Build the result by taking one numerator factor and one denominator factor together. */ for (int i = 1; i <= r; i++) { answer = answer * (n - r + i) / i; } return answer; }};// Driver code startsint main() { int n = 5; int r = 2; Solution obj; cout << obj.computeNcrBetter(n, r) << endl; return 0;}Complexity Analysis
Time Complexity: O(min(r, n - r)), because only the smaller side of the formula is processed.
Space Complexity: O(1), because constant space is used.
Interview follow-up Questions
Choosing r items to keep is the same as choosing n - r items to leave behind. Both choices describe the same group split, so their counts are equal.
Be the first to add a comment.