Given an integer N, the task is to find the count total number of pairs (P, Q) from the range 0 ≤ P, Q < 2N, such that P OR Q = P XOR Q. Since the count can be very large, print it to modulo 109 + 7.
Examples:
Input: N = 1
Output: 3
Explanation: The pairs (P, Q) satisfying P OR Q = P XOR Q are (0, 0), (0, 1) and (1, 0). Hence output 3.Input: N = 3
Output: 27
Naive Approach: The simplest approach is to generate all possible pairs (P, Q) and count the pairs satisfying P OR Q = P XOR Q.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #define MOD 1000000007 using namespace std; // Function to calculate // (x^y)%MOD long long int power( int x, int y) { // Initialize result long long int res = 1; // Update x if it is more than or // equal to MOD x = x % MOD; while (y > 0) { // If y is odd, multiply // x with result if (y & 1) res = (res * x) % MOD; // y must be even now // y = y/2 y = y >> 1; x = (x * x) % MOD; } // Return (x^y)%MOD return res; } // Function to count total pairs void countPairs( int N) { // The upper bound is 2^N long long int high = power(2, N); // Stores the count of pairs int count = 0; // Generate all possible pairs for ( int i = 0; i < high; i++) { for ( int j = 0; j < high; j++) { // Find XOR of both integers int X = (i ^ j); // Find OR of both integers int Y = (i | j); // If both are equal if (X == Y) { // Increment count count++; } } } // Print count%MOD cout << count % MOD << endl; } // Driver Code int main() { int N = 10; // Function Call countPairs(N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { static int MOD = 1000000007 ; // Function to calculate // (x^y)%MOD static int power( int x, int y) { // Initialize result int res = 1 ; // Update x if it is more than or // equal to MOD x = x % MOD; while (y > 0 ) { // If y is odd, multiply // x with result if ((y & 1 ) != 0 ) res = (res * x) % MOD; // y must be even now // y = y/2 y = y >> 1 ; x = (x * x) % MOD; } // Return (x^y)%MOD return res; } // Function to count total pairs static void countPairs( int N) { // The upper bound is 2^N int high = power( 2 , N); // Stores the count of pairs int count = 0 ; // Generate all possible pairs for ( int i = 0 ; i < high; i++) { for ( int j = 0 ; j < high; j++) { // Find XOR of both integers int X = (i ^ j); // Find OR of both integers int Y = (i | j); // If both are equal if (X == Y) { // Increment count count++; } } } // Print count%MOD System.out.println(count % MOD); } // Driver Code public static void main(String[] args) { int N = 10 ; // Function Call countPairs(N); } } // This code is contributed by susmitakundugoaldanga. |
Python3
# Python program for the above approach # Function to calculate # (x^y)%MOD def power(x, y): MOD = 1000000007 # Initialize result res = 1 # Update x if it is more than or # equal to MOD x = x % MOD while (y > 0 ): # If y is odd, multiply # x with result if (y & 1 ): res = (res * x) % MOD # y must be even now # y = y/2 y = y >> 1 x = (x * x) % MOD # Return (x^y)%MOD return res # Function to count total pairs def countPairs( N): MOD = 1000000007 # The upper bound is 2^N high = power( 2 , N) # Stores the count of pairs count = 0 # Generate all possible pairs for i in range (high): for j in range (high): # Find XOR of both integers X = (i ^ j) # Find OR of both integers Y = (i | j) # If both are equal if (X = = Y): # Increment count count + = 1 # Print count%MOD print (count % MOD) # Driver Code N = 10 # Function Call countPairs(N) # This code is contributed by rohitsingh07052. |
C#
// C# program for the above approach using System; class GFG{ static int MOD = 1000000007; // Function to calculate // (x^y)%MOD static int power( int x, int y) { // Initialize result int res = 1; // Update x if it is more than or // equal to MOD x = x % MOD; while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) != 0) res = (res * x) % MOD; // y must be even now // y = y/2 y = y >> 1; x = (x * x) % MOD; } // Return (x^y)%MOD return res; } // Function to count total pairs static void countPairs( int N) { // The upper bound is 2^N int high = power(2, N); // Stores the count of pairs int count = 0; // Generate all possible pairs for ( int i = 0; i < high; i++) { for ( int j = 0; j < high; j++) { // Find XOR of both integers int X = (i ^ j); // Find OR of both integers int Y = (i | j); // If both are equal if (X == Y) { // Increment count count++; } } } // Print count%MOD Console.WriteLine(count % MOD); } // Driver Code static public void Main() { int N = 10; // Function Call countPairs(N); } } // This code is contributed by susmitakundugoaldanga. |
Javascript
<script> // Javascript program for the above approach MOD = 1000000007; // Function to calculate // (x^y)%MOD function power(x , y) { // Initialize result var res = 1; // Update x if it is more than or // equal to MOD x = x % MOD; while (y > 0) { // If y is odd, multiply // x with result if ((y & 1) != 0) res = (res * x) % MOD; // y must be even now // y = y/2 y = y >> 1; x = (x * x) % MOD; } // Return (x^y)%MOD return res; } // Function to count total pairs function countPairs(N) { // The upper bound is 2^N var high = power(2, N); // Stores the count of pairs var count = 0; // Generate all possible pairs for (i = 0; i < high; i++) { for (j = 0; j < high; j++) { // Find XOR of both integers var X = (i ^ j); // Find OR of both integers var Y = (i | j); // If both are equal if (X == Y) { // Increment count count++; } } } // Print count%MOD document.write(count % MOD); } // Driver Code var N = 10; // Function Call countPairs(N); // This code contributed by Rajput-Ji </script> |
59049
Time Complexity: O(22*N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the following observations:
- Consider the pair as (P, Q). Fix P and then find all the Qs which satisfy this equation. So, all the bits which are set in P will be unset in Q.
- For each unset bit in P, there are two options i.e., the corresponding bits in Q can be 0 or 1.
- So for any P, if the number of unset bits in P is u(P) then the number of Q’s will be ans1 = 2^u(P).
- Iterate over the range [0, N] using the variable i, then for each 2i will have a contribution of NCi. Let this count be ans2.
- So the count of pairs is given by ∑(ans1*ans2) = (1 + 2)N = 3N.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> #define MOD 1000000007 using namespace std; // Function to find the value of (x^y)%MOD long long int power( int x, int y) { // Initialize result long long int res = 1; // Update x if it is more than or // equal to MOD x = x % MOD; while (y > 0) { // If y is odd, multiply // x with result if (y & 1) res = (res * x) % MOD; // y must be even now, then // update y/2 y = y >> 1; x = (x * x) % MOD; } // Return (x^y)%MOD return res; } // Function to count total pairs void countPairs( int N) { // Finding 3^N % 10^9+7 cout << power(3, N); } // Driver Code int main() { int N = 10; // Function Call countPairs(N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { static final int MOD = 1000000007 ; // Function to find the value of (x^y)%MOD static int power( int x, int y) { // Initialize result int res = 1 ; // Update x if it is more than or // equal to MOD x = x % MOD; while (y > 0 ) { // If y is odd, multiply // x with result if (y % 2 == 1 ) res = (res * x) % MOD; // y must be even now, then // update y/2 y = y >> 1 ; x = (x * x) % MOD; } // Return (x^y)%MOD return res; } // Function to count total pairs static void countPairs( int N) { // Finding 3^N % 10^9+7 System.out.print(power( 3 , N)); } // Driver Code public static void main(String[] args) { int N = 10 ; // Function Call countPairs(N); } } // This code is contributed by shikhasingrajput |
Python3
# Python program for the above approach MOD = 1000000007 ; # Function to find the value of (x^y)%MOD def power(x, y): # Initialize result res = 1 ; # Update x if it is more than or # equal to MOD x = x % MOD; while (y > 0 ): # If y is odd, multiply # x with result if (y % 2 = = 1 ): res = (res * x) % MOD; # y must be even now, then # update y/2 y = y >> 1 ; x = (x * x) % MOD; # Return (x^y)%MOD return res; # Function to count total pairs def countPairs(N): # Finding 3^N % 10^9+7 print (power( 3 , N)); # Driver Code if __name__ = = '__main__' : N = 10 ; # Function Call countPairs(N); # This code is contributed by 29AjayKumar |
C#
// C# program for the above approach using System; public class GFG { static readonly int MOD = 1000000007; // Function to find the value of (x^y)%MOD static int power( int x, int y) { // Initialize result int res = 1; // Update x if it is more than or // equal to MOD x = x % MOD; while (y > 0) { // If y is odd, multiply // x with result if (y % 2== 1) res = (res * x) % MOD; // y must be even now, then // update y/2 y = y >> 1; x = (x * x) % MOD; } // Return (x^y)%MOD return res; } // Function to count total pairs static void countPairs( int N) { // Finding 3^N % 10^9+7 Console.Write(power(3, N)); } // Driver Code public static void Main(String[] args) { int N = 10; // Function Call countPairs(N); } } // This code contributed by shikhasingrajput |
Javascript
<script> // Javascript program for the above approach var MOD = 1000000007; // Function to find the value of (x^y)%MOD function power(x , y) { // Initialize result var res = 1; // Update x if it is more than or // equal to MOD x = x % MOD; while (y > 0) { // If y is odd, multiply // x with result if (y % 2 == 1) res = (res * x) % MOD; // y must be even now, then // update y/2 y = y >> 1; x = (x * x) % MOD; } // Return (x^y)%MOD return res; } // Function to count total pairs function countPairs(N) { // Finding 3^N % 10^9+7 document.write(power(3, N)); } // Driver Code var N = 10; // Function Call countPairs(N); // This code contributed by Rajput-Ji </script> |
59049
Time Complexity: O(log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!