Given three numbers N, A, B. The task is to count the number of ways to select things such that there exists no set of size either A or B. Answer can be very large. So, output answer modulo 109+7. Note: Empty set is not consider as one of the way. Examples:
Input: N = 4, A = 1, B = 3 Output: 7 Explanation: The number of ways to form sets of size 2 are 6 (4C2). The number of ways to form sets of size 4 are 1 (4C4). Input: N = 10, A = 4, B = 9 Output: 803
Approach: The idea is to first find the number of ways including sets of size including A, B and empty sets. Then the remove the number of the sets of size A, B and empty sets. Below is the implementation of the above approach:
CPP
// C++ program to find number of sets without size A and B#include <bits/stdc++.h>using namespace std;#define mod (int)(1e9 + 7)// Function to find a^m1int power(int a, int m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (1LL * a * a) % mod; // If m1 is odd, then return a * a^m1/2 * a^m1/2 else if (m1 & 1) return (1LL * a * power(power(a, m1 / 2), 2)) % mod; else return power(power(a, m1 / 2), 2) % mod;}// Function to find factorial of a numberint factorial(int x){ int ans = 1; for (int i = 1; i <= x; i++) ans = (1LL * ans * i) % mod; return ans;}// Function to find inverse of xint inverse(int x){ return power(x, mod - 2);}// Function to find nCrint binomial(int n, int r){ if (r > n) return 0; int ans = factorial(n); ans = (1LL * ans * inverse(factorial(r))) % mod; ans = (1LL * ans * inverse(factorial(n - r))) % mod; return ans;}// Function to find number of sets without size a and bint number_of_sets(int n, int a, int b){ // First calculate all sets int ans = power(2, n); // Remove sets of size a ans = ans - binomial(n, a); if (ans < 0) ans += mod; // Remove sets of size b ans = ans - binomial(n, b); // Remove empty set ans--; if (ans < 0) ans += mod; // Return the required answer return ans;}// Driver codeint main(){ int N = 4, A = 1, B = 3; // Function call cout << number_of_sets(N, A, B); return 0;} |
Java
// Java program to find number of sets without size A and Bimport java.util.*;class GFG{static final int mod =(int)(1e9 + 7); // Function to find a^m1static int power(int a, int m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (int) ((1L * a * a) % mod); // If m1 is odd, then return a * a^m1/2 * a^m1/2 else if (m1 % 2 == 1) return (int) ((1L * a * power(power(a, m1 / 2), 2)) % mod); else return power(power(a, m1 / 2), 2) % mod;} // Function to find factorial of a numberstatic int factorial(int x){ int ans = 1; for (int i = 1; i <= x; i++) ans = (int) ((1L * ans * i) % mod); return ans;} // Function to find inverse of xstatic int inverse(int x){ return power(x, mod - 2);} // Function to find nCrstatic int binomial(int n, int r){ if (r > n) return 0; int ans = factorial(n); ans = (int) ((1L * ans * inverse(factorial(r))) % mod); ans = (int) ((1L * ans * inverse(factorial(n - r))) % mod); return ans;} // Function to find number of sets without size a and bstatic int number_of_sets(int n, int a, int b){ // First calculate all sets int ans = power(2, n); // Remove sets of size a ans = ans - binomial(n, a); if (ans < 0) ans += mod; // Remove sets of size b ans = ans - binomial(n, b); // Remove empty set ans--; if (ans < 0) ans += mod; // Return the required answer return ans;} // Driver codepublic static void main(String[] args){ int N = 4, A = 1, B = 3; // Function call System.out.print(number_of_sets(N, A, B)); }}// This code contributed by sapnasingh4991 |
Python3
# Python3 program to find number of # sets without size A and Bmod = 10**9 + 7# Function to find a^m1def power(a, m1): if (m1 == 0): return 1 elif (m1 == 1): return a elif (m1 == 2): return (a * a) % mod # If m1 is odd, then return a * a^m1/2 * a^m1/2 elif (m1 & 1): return (a * power(power(a, m1 // 2), 2)) % mod else: return power(power(a, m1 // 2), 2) % mod# Function to find factorial of a numberdef factorial(x): ans = 1 for i in range(1, x + 1): ans = (ans * i) % mod return ans# Function to find inverse of xdef inverse(x): return power(x, mod - 2)# Function to find nCrdef binomial(n, r): if (r > n): return 0 ans = factorial(n) ans = (ans * inverse(factorial(r))) % mod ans = (ans * inverse(factorial(n - r))) % mod return ans# Function to find number of sets without size a and bdef number_of_sets(n, a, b): # First calculate all sets ans = power(2, n) # Remove sets of size a ans = ans - binomial(n, a) if (ans < 0): ans += mod # Remove sets of size b ans = ans - binomial(n, b) # Remove empty set ans -= 1 if (ans < 0): ans += mod # Return the required answer return ans# Driver codeif __name__ == '__main__': N = 4 A = 1 B = 3 # Function call print(number_of_sets(N, A, B))# This code is contributed by mohit kumar 29 |
C#
// C# program to find number of sets without size A and Busing System;class GFG{static readonly int mod =(int)(1e9 + 7); // Function to find a^m1static int power(int a, int m1){ if (m1 == 0) return 1; else if (m1 == 1) return a; else if (m1 == 2) return (int) ((1L * a * a) % mod); // If m1 is odd, then return a * a^m1/2 * a^m1/2 else if (m1 % 2 == 1) return (int) ((1L * a * power(power(a, m1 / 2), 2)) % mod); else return power(power(a, m1 / 2), 2) % mod;} // Function to find factorial of a numberstatic int factorial(int x){ int ans = 1; for (int i = 1; i <= x; i++) ans = (int) ((1L * ans * i) % mod); return ans;} // Function to find inverse of xstatic int inverse(int x){ return power(x, mod - 2);} // Function to find nCrstatic int binomial(int n, int r){ if (r > n) return 0; int ans = factorial(n); ans = (int) ((1L * ans * inverse(factorial(r))) % mod); ans = (int) ((1L * ans * inverse(factorial(n - r))) % mod); return ans;} // Function to find number of sets without size a and bstatic int number_of_sets(int n, int a, int b){ // First calculate all sets int ans = power(2, n); // Remove sets of size a ans = ans - binomial(n, a); if (ans < 0) ans += mod; // Remove sets of size b ans = ans - binomial(n, b); // Remove empty set ans--; if (ans < 0) ans += mod; // Return the required answer return ans;} // Driver codepublic static void Main(String[] args){ int N = 4, A = 1, B = 3; // Function call Console.Write(number_of_sets(N, A, B));}} // This code is contributed by PrinciRaj1992 |
Javascript
const mod = 1e9 + 7;// Function to find a^m1function power(a, m1){ if (m1 === 0) return 1; else if (m1 === 1) return a; else if (m1 === 2) return (a * a) % mod; // If m1 is odd, then return a * a^m1/2 * a^m1/2 else if (m1 % 2 === 1) return (a * power(power(a, Math.floor(m1 / 2)), 2)) % mod; else return power(power(a, Math.floor(m1 / 2)), 2) % mod;}// Function to find factorial of a numberfunction factorial(x) { let ans = 1; for (let i = 1; i <= x; i++) ans = (ans * i) % mod; return ans;}// Function to find inverse of xfunction inverse(x) { return power(x, mod - 2);}// Function to find nCrfunction binomial(n, r) { if (r > n) return 0; let ans = factorial(n); ans = (ans * inverse(factorial(r))) % mod; ans = (ans * inverse(factorial(n - r))) % mod; return ans;}// Function to find number of sets without size a and bfunction number_of_sets(n, a, b) { // First calculate all sets let ans = power(2, n); // Remove sets of size a ans = ans - binomial(n, a); if (ans < 0) ans = (ans + mod) % mod; // Remove sets of size b ans = ans - binomial(n, b); // Remove empty set ans--; if (ans < 0) ans = (ans + mod) % mod; // Return the required answer return ans;}// Example usageconst N = 4, A = 1, B = 3;console.log(number_of_sets(N, A, B));// This code is contributed by anskalyan3. |
Output:
7
Time complexity: O(nlogn) because using a for loop and power function
Auxiliary Space: O(logn)
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!
