Count all ordered pairs (A, B) such that intersection of A and B becomes K
Given a positive integer k and an array arr[] of size n contains distinct elements, the task is to find the number of ordered pairs (A, B) that can be made where A and B are subsets of the given array arr[] and A ∩ B contains exactly k (1 <= k <= n).
Example:
Input: arr = {1, 2}, k = 1
Output: 6
Explanation: The subsets of the array are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. The ordered pairs (A, B) where A ∩ B contains k elements: ({1}, {1}), ({2}, {2}), ({1, 2}, {2}), ({2}, {1,2}), ({1}, {1, 2}), ({1, 2}, {1})Input: arr = {1, 2, 3}, k = 2
Output: 9
Approach:
Select k elements from n elements (nCk) and put in both subset A, B. Rest elements have 3 options it will either be included in A, B, or not included in either A or B. Hence, there would be 3(n – k) possible combinations for given array of size n.
Steps-by-step approach:
- Create a function nCr() that calculates the binomial coefficient “n choose r.”
- Calculate the binomial coefficient inside the nCr function using the formula nCr = n! / (r! * (n-r)!).
- Calculates the number of ordered pairs (A, B) where A and B are subsets of a given array arr, and A ∩ B contains exactly k elements.
- Return the result of nCr(n, k) * pow(3, n – k).
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Define the modulo constant const long long MOD = 1e9 + 7; // Function to find nCr long long nCr( long long n, long long r) { long long sum = 1; // Calculate the value of n choose r using the binomial // coefficient formula for ( long long i = 1; i <= r; i++) { sum = sum * (n - r + i) / i; } return sum; } // Function to calculate power using binary exponentiation long long binpow( long long base, long long exp ) { base %= MOD; // Take modulo of base to keep it within // range long long result = 1; // Initialize result while ( exp > 0) { // Loop until exponent is greater than 0 if ( exp & 1) // If exponent is odd result = (result * base) % MOD; // Multiply result with base base = (base * base) % MOD; // Square the base exp >>= 1; // Divide the exponent by 2 } return result; // Return the final result } // Function to find the number of ordered pairs (A, B) that // can be made where A and B are subsets of the given array // arr[] and A ∩ B contains exactly k long long solve( long long n, long long k, vector< long long >& arr) { return nCr(n, k) * binpow(3, n - k); } int main() { long long n = 3, k = 2; vector< long long > arr = { 1, 2, 3 }; cout << solve(n, k, arr); return 0; } |
Java
import java.util.*; public class Main { // Define the modulo constant static final long MOD = 1000000007 ; // Function to find nCr static long nCr( long n, long r) { long sum = 1 ; // Calculate the value of n choose r using the binomial // coefficient formula for ( long i = 1 ; i <= r; i++) { sum = sum * (n - r + i) / i; } return sum; } // Function to calculate power using binary exponentiation static long binpow( long base, long exp) { base %= MOD; // Take modulo of base to keep it within range long result = 1 ; // Initialize result while (exp > 0 ) { // Loop until exponent is greater than 0 if ((exp & 1 ) == 1 ) // If exponent is odd result = (result * base) % MOD; // Multiply result with base base = (base * base) % MOD; // Square the base exp >>= 1 ; // Divide the exponent by 2 } return result; // Return the final result } // Function to find the number of ordered pairs (A, B) that // can be made where A and B are subsets of the given array // arr[] and A ∩ B contains exactly k static long solve( long n, long k, List<Long> arr) { return nCr(n, k) * binpow( 3 , n - k) % MOD; } public static void main(String[] args) { long n = 3 , k = 2 ; List<Long> arr = Arrays.asList(1L, 2L, 3L); System.out.println(solve(n, k, arr)); } } |
Python3
# Function to calculate nCr def nCr(n, r): sum = 1 # Calculate the value of n choose r using the binomial # coefficient formula for i in range ( 1 , r + 1 ): sum = sum * (n - r + i) / / i return sum # Function to calculate power using binary exponentiation def binpow(base, exp, MOD): base % = MOD # Take modulo of base to keep it within range result = 1 # Initialize result while exp > 0 : # Loop until exponent is greater than 0 if exp & 1 : # If exponent is odd result = (result * base) % MOD # Multiply result with base base = (base * base) % MOD # Square the base exp >> = 1 # Divide the exponent by 2 return result # Return the final result # Function to find the number of ordered pairs (A, B) that # can be made where A and B are subsets of the given array # arr[] and A ∩ B contains exactly k def solve(n, k, arr): MOD = 10 * * 9 + 7 return nCr(n, k) * binpow( 3 , n - k, MOD) # Main function def main(): n = 3 k = 2 arr = [ 1 , 2 , 3 ] print (solve(n, k, arr)) if __name__ = = "__main__" : main() # This code is contributed by shivamgupta310570 |
C#
using System; using System.Collections.Generic; class Program { // Define the modulo constant const long MOD = 1000000007; // Function to find nCr static long nCr( long n, long r) { long sum = 1; // Calculate the value of n choose r using the binomial // coefficient formula for ( long i = 1; i <= r; i++) { sum = sum * (n - r + i) / i; } return sum; } // Function to calculate power using binary exponentiation static long Binpow( long baseNum, long exponent) { long baseVal = baseNum % MOD; // Take modulo of base to keep it within range long result = 1; // Initialize result // Loop until exponent is greater than 0 while (exponent > 0) { // If exponent is odd if ((exponent & 1) == 1) result = (result * baseVal) % MOD; // Multiply result with base baseVal = (baseVal * baseVal) % MOD; // Square the base exponent >>= 1; // Divide the exponent by 2 } return result; // Return the final result } // Function to find the number of ordered pairs (A, B) that // can be made where A and B are subsets of the given array // arr[] and A ∩ B contains exactly k static long Solve( long n, long k, List< long > arr) { return nCr(n, k) * Binpow(3, n - k); } static void Main( string [] args) { long n = 3, k = 2; List< long > arr = new List< long >() { 1, 2, 3 }; Console.WriteLine(Solve(n, k, arr)); } } |
Javascript
// JavaScript Implementation // Function to find nCr function nCr(n, r) { let sum = 1; // Calculate the value of n choose r using the binomial // coefficient formula for (let i = 1; i <= r; i++) { sum = sum * (n - r + i) / i; } return sum; } // Function to calculate power using binary exponentiation function binpow(base, exp) { const MOD = 1e9 + 7; base %= MOD; // Take modulo of base to keep it within range let result = 1; // Initialize result while (exp > 0) { // Loop until exponent is greater than 0 if (exp & 1) // If exponent is odd result = (result * base) % MOD; // Multiply result with base base = (base * base) % MOD; // Square the base exp >>= 1; // Divide the exponent by 2 } return result; // Return the final result } // Function to find the number of ordered pairs (A, B) that // can be made where A and B are subsets of the given array // arr[] and A ∩ B contains exactly k function solve(n, k, arr) { return nCr(n, k) * binpow(3, n - k); } const n = 3; const k = 2; const arr = [1, 2, 3]; console.log(solve(n, k, arr)); // This code is contributed by Tapesh(tapeshdu420) |
9
Time Complexity: O(k)
Auxiliary Space: O(log(n – k)), due to recusive call stack of pow().
Contact Us