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 |
27
Time Complexity: O(log(n))
Auxiliary Space: O(log(n))
Contact Us