Count of triplets whose XOR has even set bits in range [L, R] for Q queries
Given an array arr[] of size N, and an array Q[] consisting of M queries of type {L, R}, the task is to print the count of triplets whose XOR has an even number of set bits in the range [L, R], for each of the M queries.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}, N = 5, Q[] = {{1, 4}, {3, 4}}, M = 2
Output: 3
0
Explanation:
Perform the query as following:
- Query(1, 4): Print 3. The triplets whose xor has an even number of set bits are {1, 2, 3}, {1, 3, 4} and {2, 3, 4}.
- Query(3, 4): Print 0. There are no triplets that satisfy the condition.
Input: arr[] = {3, 3, 3}, N = 2, Q[] = {{1, 3}}, M = 1
Output: 1
Approach: The given problem can be solved based on the following observations:
- The XOR of two numbers X and Y i.e X^Y can have an even number of set bits only if:
- Both X and Y have an even number of set bits.
- Both X and Y have an odd number of set bits.
- Thus, there are only cases, where the XOR of three numbers has an even number of set bits, which are:
- All three numbers have an even number of set bits.
- Exactly two of them have an odd number of set bits and the other has an even number of set bits.
- Therefore, the problem can be solved with the concept of prefix arrays by applying the above observations.
Follow the steps below to solve the problem:
- Initialize a prefix array say preo[] of size N+1, where preo[i] stores the number of elements up to index i, that have an odd number of set bits.
- Create another prefix array say pree of size N+1, where pree[i] stores the number of elements up to index i, that have an even number of set bits.
- Traverse the array arr[], and do the following:
- Use the __builtin_popcount() function to calculate the number of set bits in the current element.
- If the number of set bits is odd, increment preo[i]
- Otherwise, increment pree[i]
- Traverse the array Q[] and perform the following steps:
- Calculate the number of elements that have an odd number of set bits and store it in a variable say odd, using the preo[] array.
- Calculate the number of elements that have an even number of set bits and store it in a variable say even, using the pree [] array.
- Initialize a variable ans to 0 to store the count of triplets.
- If even is not less than 3, add evenC3 to ans.
- If even is not less than 1 and odd is not less than 2, add (oddC2)*(evenC1) to ans.
- Finally, print the count of triplets obtained in ans for the current query {L, R}.
Below is an implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Utility function to calculate NCR int NCR( int N, int R) { if (R > N - R) R = N - R; int ans = 1; for ( int i = 1; i <= R; i++) { ans *= N - R + i; ans /= i; } return ans; } // Function to answer queries about // the number of triplets in range // whose XOR has an even number of // set bits void solveXorTriplets( int arr[], int N, vector<pair< int , int > > Q, int M) { // Prefix arrays to store // number that have odd // and even setbits int preo[N + 1] = { 0 }; int pree[N + 1] = { 0 }; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Update preo[i + 1] += preo[i]; pree[i + 1] += pree[i]; // Find bits in current // element int setbits = __builtin_popcount(arr[i]); // If number of setbits // is odd if (setbits % 2) preo[i + 1]++; // Otherwise else pree[i + 1]++; } // Traverse the query Q[][] for ( int i = 0; i < M; i++) { // Stores Left boundary int L = Q[i].first; // Stores Right boundary int R = Q[i].second; // Stores number of elements // that have odd set bits in // the given range int odd = preo[R] - preo[L - 1]; // Store number of elements // that have even set bits // in given range int even = pree[R] - pree[L - 1]; // Store the count // of the triplets int ans = 0; // If even is greater // than ore equal to 3 if (even >= 3) ans += NCR(even, 3); // If odd is greater than // or equal to and even is // greater than or equal to // 1 if (odd >= 2 && even >= 1) ans += NCR(odd, 2) * NCR(even, 1); // Print the answer // for current query cout << ans << endl; } } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof (arr) / sizeof (arr[0]); vector<pair< int , int > > Q = { { 1, 4 }, { 3, 4 } }; int M = Q.size(); solveXorTriplets(arr, N, Q, M); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ static class pair { int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Utility function to calculate NCR static int NCR( int N, int R) { if (R > N - R) R = N - R; int ans = 1 ; for ( int i = 1 ; i <= R; i++) { ans *= N - R + i; ans /= i; } return ans; } // Function to answer queries about // the number of triplets in range // whose XOR has an even number of // set bits static void solveXorTriplets( int arr[], int N, Vector<pair> Q, int M) { // Prefix arrays to store // number that have odd // and even setbits int preo[] = new int [N + 1 ]; int pree[] = new int [N + 1 ]; // Traverse the array arr[] for ( int i = 0 ; i < N; i++) { // Update preo[i + 1 ] += preo[i]; pree[i + 1 ] += pree[i]; // Find bits in current // element int setbits = Integer.bitCount(arr[i]); // If number of setbits // is odd if (setbits % 2 != 0 ) preo[i + 1 ]++; // Otherwise else pree[i + 1 ]++; } // Traverse the query Q[][] for ( int i = 0 ; i < M; i++) { // Stores Left boundary int L = Q.elementAt(i).first; // Stores Right boundary int R = Q.elementAt(i).second; // Stores number of elements // that have odd set bits in // the given range int odd = preo[R] - preo[L - 1 ]; // Store number of elements // that have even set bits // in given range int even = pree[R] - pree[L - 1 ]; // Store the count // of the triplets int ans = 0 ; // If even is greater // than ore equal to 3 if (even >= 3 ) ans += NCR(even, 3 ); // If odd is greater than // or equal to and even is // greater than or equal to // 1 if (odd >= 2 && even >= 1 ) ans += NCR(odd, 2 ) * NCR(even, 1 ); // Print the answer // for current query System.out.println(ans); } } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int N = arr.length; Vector<pair> Q = new Vector<>(); Q.add( new pair( 1 , 4 )); Q.add( new pair( 3 , 4 )); int M = Q.size(); solveXorTriplets(arr, N, Q, M); } } // This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach # Utility function to calculate NCR def NCR(N, R): if (R > N - R): R = N - R ans = 1 for i in range ( 1 ,R + 1 ): ans * = N - R + i ans / / = i return ans # Function to answer queries about # the number of triplets in range # whose XOR has an even number of # set bits def solveXorTriplets(arr, N, Q, M): # Prefix arrays to store # number that have odd # and even setbits preo = [ 0 ] * (N + 1 ) pree = [ 0 ] * (N + 1 ) # Traverse the array arr[] for i in range (N): preo[i + 1 ] + = preo[i] pree[i + 1 ] + = pree[i] # Find bits in current # element setbits = bin (arr[i]).count( '1' ) # If number of setbits # is odd if (setbits % 2 ): preo[i + 1 ] + = 1 # Otherwise else : pree[i + 1 ] + = 1 # Traverse the query Q[][] for i in range (M): # Stores Left boundary L = Q[i][ 0 ] # Stores Right boundary R = Q[i][ 1 ] # Stores number of elements # that have odd set bits in # the given range odd = preo[R] - preo[L - 1 ] # Store number of elements # that have even set bits # in given range even = pree[R] - pree[L - 1 ] # Store the count # of the triplets ans = 0 # If even is greater # than ore equal to 3 if (even > = 3 ): ans + = NCR(even, 3 ) # If odd is greater than # or equal to and even is # greater than or equal to # 1 if (odd > = 2 and even > = 1 ): ans + = NCR(odd, 2 ) * NCR(even, 1 ) # Print answer # for current query print (ans) # Driver Code if __name__ = = '__main__' : arr = [ 1 , 2 , 3 , 4 , 5 ] N = len (arr) Q = [ [ 1 , 4 ], [ 3 , 4 ] ] M = len (Q) solveXorTriplets(arr, N, Q, M) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class pair{ int first, second; pair( int first, int second) { this .first = first; this .second = second; } public static int BitCount( int n) { var count = 0; while (n != 0) { count++; n &= (n - 1); //walking through all the bits which are set to one } return count; } // Utility function to calculate NCR static int NCR( int N, int R) { if (R > N - R) R = N - R; int ans = 1; for ( int i = 1; i <= R; i++) { ans *= N - R + i; ans /= i; } return ans; } // Function to answer queries about // the number of triplets in range // whose XOR has an even number of // set bits static void solveXorTriplets( int [] arr, int N, List<pair> Q, int M) { // Prefix arrays to store // number that have odd // and even setbits int [] preo = new int [N + 1]; int [] pree = new int [N + 1]; // Traverse the array arr[] for ( int i = 0; i < N; i++) { // Update preo[i + 1] += preo[i]; pree[i + 1] += pree[i]; // Find bits in current // element int setbits = BitCount(arr[i]); // If number of setbits // is odd if (setbits % 2 != 0) preo[i + 1]++; // Otherwise else pree[i + 1]++; } // Traverse the query Q[][] for ( int i = 0; i < M; i++) { // Stores Left boundary int L = Q[i].first; // Stores Right boundary int R = Q[i].second; // Stores number of elements // that have odd set bits in // the given range int odd = preo[R] - preo[L - 1]; // Store number of elements // that have even set bits // in given range int even = pree[R] - pree[L - 1]; // Store the count // of the triplets int ans = 0; // If even is greater // than ore equal to 3 if (even >= 3) ans += NCR(even, 3); // If odd is greater than // or equal to and even is // greater than or equal to // 1 if (odd >= 2 && even >= 1) ans += NCR(odd, 2) * NCR(even, 1); // Print the answer // for current query Console.WriteLine(ans); } } // Driver Code public static void Main() { int [] arr = { 1, 2, 3, 4, 5 }; int N = arr.Length; List<pair> Q = new List<pair>(); Q.Add( new pair(1, 4)); Q.Add( new pair(3, 4)); int M = Q.Count; solveXorTriplets(arr, N, Q, M); } } // This code is contributed by ShubhamSingh10 |
Javascript
<script> // JavaScript program for the above approach function bitCount1(n) { return n.toString(2).match(/1/g).length } // Utility function to calculate NCR function NCR(N, R) { if (R > N - R) R = N - R; var ans = 1; for ( var i = 1; i <= R; i++) { ans *= N - R + i; ans /= i; } return ans; } // Function to answer queries about // the number of triplets in range // whose XOR has an even number of // set bits function solveXorTriplets(arr, N, Q, M) { // Prefix arrays to store // number that have odd // and even setbits var preo = new Array(N+1).fill(0); var pree = new Array(N+1).fill(0); // Traverse the array arr[] for ( var i = 0; i < N; i++) { // Update preo[i + 1] += preo[i]; pree[i + 1] += pree[i]; // Find bits in current // element var setbits = bitCount1(arr[i]); // If number of setbits // is odd if (setbits % 2) preo[i + 1]++; // Otherwise else pree[i + 1]++; } // Traverse the query Q[][] for ( var i = 0; i < M; i++) { // Stores Left boundary var L = Q[i][0]; // Stores Right boundary var R = Q[i][1]; // Stores number of elements // that have odd set bits in // the given range var odd = preo[R] - preo[L - 1]; // Store number of elements // that have even set bits // in given range var even = pree[R] - pree[L - 1]; // Store the count // of the triplets var ans = 0; // If even is greater // than ore equal to 3 if (even >= 3) ans += NCR(even, 3); // If odd is greater than // or equal to and even is // greater than or equal to // 1 if (odd >= 2 && even >= 1) ans += NCR(odd, 2) * NCR(even, 1); // Print the answer // for current query document.write(ans + "<br>" ); } } // Driver Code var arr = [1, 2, 3, 4, 5 ]; var N = arr.length; var Q = [ [ 1, 4 ], [ 3, 4 ] ]; var M = Q.length; solveXorTriplets(arr, N, Q, M); // This code is contributed by Shubhamsingh10 </script> |
Output
3 0
Time Complexity: O(N+M)
Auxiliary Space: O(N)
Contact Us