Given three values, N, L and R, the task is to calculate the sum of binomial coefficients (nCr) for all values of r from L to R.
Examples:
Input: N = 5, L = 0, R = 3
Output: 26
Explanation: Sum of 5C0 + 5C1 + 5C2 + 5C3 = 1 + 5 + 10 + 10 = 26.Input: N = 3, L = 3, R = 3
Output: 1
Approach(Using factorial function): Solve this problem by straightforward calculating nCr by using the formula n! / (r!(n−r)!) and calculating factorial recursively for every value of r from L to R.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the factorial // of a given numberlong long factorial(long long num){ if (num == 0 || num == 1) return 1; else return num * factorial(num - 1);}// Function to calculate the sum // of binomial coefficients(nCr) for // all values of r from L to Rlong long sumOfnCr(int n, int R, int L){ long long r; long long res = 0; for (r = L; r <= R; r++) res += (factorial(n) / (factorial(r) * factorial(n - r))); return res;}// Driver Codeint main(){ int N = 5, L = 0, R = 3; cout << sumOfnCr(N, R, L); return 0;} |
Java
// JAVA program for the above approachimport java.io.*;class GFG { // Function to find the factorial // of a given number static long factorial(long num) { if (num == 0 || num == 1) return 1; else return num * factorial(num - 1); } // Function to calculate the sum // of binomial coefficients(nCr) for // all values of r from L to R static long sumOfnCr(int n, int R, int L) { long r; long res = 0; for (r = L; r <= R; r++) res += (factorial(n) / (factorial(r) * factorial(n - r))); return res; } // Driver Code public static void main(String[] args) { int N = 5, L = 0, R = 3; long ans = sumOfnCr(N, R, L); System.out.println(ans); }}// This code is contributed by Taranpreet |
Python3
# Python code for the above approach # Function to find the factorial # of a given numberdef factorial(num): if (num == 0 or num == 1): return 1; else: return num * factorial(num - 1);# Function to calculate the sum # of binomial coefficients(nCr) for # all values of r from L to Rdef sumOfnCr(n, R, L): res = 0; for r in range(L, R + 1): res += (factorial(n) / (factorial(r) * factorial(n - r))); return res;# Driver CodeN = 5L = 0R = 3;print((int)(sumOfnCr(N, R, L)))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG { // Function to find the factorial // of a given number static long factorial(long num) { if (num == 0 || num == 1) return 1; else return num * factorial(num - 1); } // Function to calculate the sum // of binomial coefficients(nCr) for // all values of r from L to R static long sumOfnCr(int n, int R, int L) { long r; long res = 0; for (r = L; r <= R; r++) res += (factorial(n) / (factorial(r) * factorial(n - r))); return res; } // Driver Code public static void Main() { int N = 5, L = 0, R = 3; Console.Write(sumOfnCr(N, R, L)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to find the factorial // of a given number function factorial(num) { if (num == 0 || num == 1) return 1; else return num * factorial(num - 1); } // Function to calculate the sum // of binomial coefficients(nCr) for // all values of r from L to R function sumOfnCr(n, R, L) { let r; let res = 0; for (r = L; r <= R; r++) res += (factorial(n) / (factorial(r) * factorial(n - r))); return res; } // Driver Code let N = 5, L = 0, R = 3; document.write(sumOfnCr(N, R, L)); // This code is contributed by Potta Lokesh </script> |
Output
26
Time Complexity: O(N * (R – L))
Auxiliary Space: O(N)
Approach (Without using factorial function): This approach for finding the sum of binomial coefficients (nCr) for all values of r from L to R can be implemented using two nested loops. The outer loop will iterate from L to R, and the inner loop will calculate the binomial coefficient for each value of r using the formula:
nCr = n! / (r! * (n-r)!)
where n is the given number, r is the current value of the inner loop, and ! denotes the factorial function.
The sum of all binomial coefficients can be accumulated in a variable initialized to zero before the loops start.
Steps to implement the above approach:
- Declare and initialize the variables N, L, and R respectively.
- Call the sumOfnCr function, passing N, R, and L as arguments.
- Within the sumOfnCr function, declare a long long variable named res and initialize it to 0.
- Start a for loop with a variable r, which runs from L to R.
- Within the for loop, declare a long long variable named nCr and initialize it to 1.
- Start another for loop with a variable i, which runs from 1 to r.
- Within the inner for loop, multiply nCr by (n-i+1) and then divide it by i.
- After the inner for loop ends, add nCr to the res variable.
- After the outer for loop ends, return the res variable.
- End the sumOfnCr function.
- Print the result of the sumOfnCr function using cout.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the sum// of binomial coefficients(nCr) for// all values of r from L to Rlong long sumOfnCr(int n, int R, int L){ long long res = 0; for (int r = L; r <= R; r++) { long long nCr = 1; for (int i = 1; i <= r; i++) { nCr *= (n - i + 1); nCr /= i; } res += nCr; } return res;}// Driver Codeint main(){ int N = 5, L = 0, R = 3; cout << sumOfnCr(N, R, L); return 0;} |
Java
import java.math.BigInteger;public class BinomialCoefficientSum { // Function to calculate the sum of binomial coefficients (nCr) // for all values of r from L to R public static BigInteger sumOfnCr(int n, int R, int L) { // Initialize the result as zero BigInteger res = BigInteger.ZERO; // Iterate through all values of r from L to R for (int r = L; r <= R; r++) { // Initialize nCr as 1 BigInteger nCr = BigInteger.ONE; // Calculate nCr using multiplicative formula for (int i = 1; i <= r; i++) { // Multiplicative formula for nCr: nCr = (n - i + 1) / i * nCr nCr = nCr.multiply(BigInteger.valueOf(n - i + 1)).divide(BigInteger.valueOf(i)); } // Add the calculated nCr to the result res = res.add(nCr); } // Return the final result return res; } public static void main(String[] args) { // Input values int N = 5, L = 0, R = 3; // Calculate and print the sum of binomial coefficients System.out.println(sumOfnCr(N, R, L)); }} |
Python3
# Function to calculate the sum# of binomial coefficients(nCr) for# all values of r from L to Rdef sumOfnCr(n, R, L): res = 0 for r in range(L, R+1): nCr = 1 for i in range(1, r+1): nCr *= (n - i + 1) nCr //= i res += nCr return res# Driver CodeN = 5L = 0R = 3print(sumOfnCr(N, R, L)) |
C#
using System;class Program{ // Function to calculate the sum of binomial coefficients(nCr) for // all values of r from L to R static long SumOfnCr(int n, int R, int L) { long res = 0; for (int r = L; r <= R; r++) { long nCr = 1; for (int i = 1; i <= r; i++) { nCr *= (n - i + 1); nCr /= i; } res += nCr; } return res; } static void Main(string[] args) { int N = 5, L = 0, R = 3; Console.WriteLine(SumOfnCr(N, R, L)); }}// This code is contributed by shivamgupta310570 |
Javascript
// Javascript code addition // Function to calculate the sum// of binomial coefficients(nCr) for// all values of r from L to Rfunction sumOfnCr(n, R, L) { let res = 0; for (let r = L; r <= R; r++) { let nCr = 1; for (let i = 1; i <= r; i++) { nCr *= (n - i + 1); nCr /= i; } res += nCr; } return res;}// Driver Codelet N = 5, L = 0, R = 3;console.log(sumOfnCr(N, R, L));// The code is contributed by Nidhi goel. |
Output
26
Time Complexity: O(N * (R – L))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
