Horje
Count all ordered pairs (A, B) such that A and B are disjoint

Given 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 = Φ (i.e, Both A and B subset should be disjoint or no common elements between them).

Example:

Input: arr = {1, 2}
Output: 9
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 and B disjoint subsets are: ({}, {}), ({}, {1}), ({}, {2}), ({1}, {}), ({2}, {}), ({1, 2}, {}), ({}, {1, 2}, ({1}, {2}, ({2}, {1})

Input: arr = {1, 2, 3}
Output: 27

Approach:

Every element has three options, It will either be included in A, B, or not included in either A or B. Hence, there would be 3^n possible combinations for given array of size n.

Steps-by-step approach:

  • Set the modulo constant MOD to 1e9 + 7.
  • Define a function binpow() that calculates the power using binary exponentiation.
    • Take the modulo of the base to keep it within the specified range.
    • Initialize result to 1.
    • Iterate until the exponent is greater than 0.
    • If the current bit of the exponent is 1, multiply the result by the base.
    • Square the base and divide the exponent by 2 in each iteration.
    • Return the final result.
  • Solve Function:
    • Define a function solve that takes an integer n and a vector arr.
    • Call binpow(3, n) to calculate (3^n) mod (1e9 + 7).
    • Return the result.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
// Define the modulo constant
const int MOD = 1e9 + 7;
 
// 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
}
 
int solve(int n, vector<int>& arr)
{
    // Use binary exponentiation instead of pow
    // This calculates (3^n) mod (1e9 + 7)
    return binpow(3, n);
}
 
int main()
{
    int n = 3; // The number of elements
    vector<int> arr = { 1, 2, 3 };
 
    // Call the solve function and print the result
    cout << solve(n, arr);
    return 0;
}

Java

import java.util.*;
 
public class Main {
    // Define the modulo constant
    static final int MOD = 1000000007;
 
    // 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
    }
 
    static int solve(int n, List<Integer> arr) {
        // Use binary exponentiation instead of pow
        // This calculates (3^n) mod (1e9 + 7)
        return (int) binpow(3, n);
    }
 
    public static void main(String[] args) {
        int n = 3; // The number of elements
        List<Integer> arr = Arrays.asList(1, 2, 3);
 
        // Call the solve function and print the result
        System.out.println(solve(n, arr));
    }
}

C#

using System;
using System.Collections.Generic;
 
public class Program
{
    // Define the modulo constant
    const int MOD = 1000000007;
 
    // Function to calculate power using binary exponentiation
    static long Binpow(long baseVal, long exp)
    {
        baseVal %= 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 * baseVal) % MOD; // Multiply result with base
            baseVal = (baseVal * baseVal) % MOD; // Square the base
            exp >>= 1; // Divide the exponent by 2
        }
        return result; // Return the final result
    }
 
    static int Solve(int n, List<int> arr)
    {
        // Use binary exponentiation instead of pow
        // This calculates (3^n) mod (1e9 + 7)
        return (int)Binpow(3, n);
    }
 
    public static void Main(string[] args)
    {
        int n = 3; // The number of elements
        List<int> arr = new List<int> { 1, 2, 3 };
 
        // Call the Solve function and print the result
        Console.WriteLine(Solve(n, arr));
    }
}

Javascript

// Define the modulo constant
const MOD = BigInt(1e9 + 7);
 
// Function to calculate power using binary exponentiation
function binpow(base, exp) {
    base %= MOD; // Take modulo of base to keep it within range
    let result = BigInt(1); // Initialize result
    while (exp > 0n) { // Loop until exponent is greater than 0
        if (exp & 1n) // If exponent is odd
            result = (result * base) % MOD; // Multiply result with base
        base = (base * base) % MOD; // Square the base
        exp >>= 1n; // Divide the exponent by 2
    }
    return result; // Return the final result
}
 
// Function to solve the problem
function solve(n, arr) {
    // Use binary exponentiation instead of pow
    // This calculates (3^n) mod (1e9 + 7)
    return binpow(3n, BigInt(n));
}
 
// Sample usage
const n = 3; // The number of elements
const arr = [1, 2, 3];
 
// Call the solve function and print the result
console.log(solve(n, arr).toString());
//This code is contributed by Monu.

Python3

# Python Implementation
 
# 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
 
def solve(n, arr):
    MOD = 10**9 + 7  # Define the modulo constant
    # Use binary exponentiation instead of pow
    # This calculates (3^n) mod (1e9 + 7)
    return binpow(3, n, MOD)
 
if __name__ == "__main__":
    n = 3  # The number of elements
    arr = [1, 2, 3]
 
    # Call the solve function and print the result
    print(solve(n, arr))
 
 
# This code is contributed by Sakshi

Output

27

Time Complexity: O(log(n))
Auxiliary Space: O(log(n))


 


Reffered: https://www.geeksforgeeks.org

Combinatorial

Related
Number of ways to color the balls (Ball Coloring) Number of ways to color the balls (Ball Coloring)
Basics of Combinatorics for Competitive Programming Basics of Combinatorics for Competitive Programming
Find the number of ways to draw the last colored ball 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) Find the number of ways in which groups can leave the lift (Rahul and The Lift)
Stars and Bars Algorithms for Competitive Programming Stars and Bars Algorithms for Competitive Programming

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



 

Horje