Count all ordered pairs (A, B) such that intersection of A and B becomes K - Coding

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 (ⁿC_k) 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)

Output

Time Complexity: O(k)
Auxiliary Space: O(log(n – k)), due to recusive call stack of pow().

Reffered: https://www.geeksforgeeks.org

Combinatorial

Related
Count all ordered pairs (A, B) such that A and B are disjoint
Number of ways to color the balls (Ball Coloring)
Basics of Combinatorics for Competitive Programming
Find the number of ways to draw the last colored ball
Find the number of ways in which groups can leave the lift (Rahul and The Lift)

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	17