Count Pairs with Specific Bit Set in two Arrays
Given two arrays A1 and A2 of size N, and Q queries, each query contains 5 numbers k, l1, r1, l2, r2. For each query, we have to return the total number of pairs (i, j), such that l1 <= i <= r1, l2 <= j <= r2, and A1[i]^A2[j] have its kth bit from the end set. 1-based indexing must be followed.
Note: The Kth bit must be checked from the end of the binary representation of a number.
Examples:
Input: N = 5, A1[] = {1, 2, 3, 4, 5}, A2[] = {1, 2, 3, 4, 5}, Q = 2, query[][] = {{2, 2, 4, 1, 3}, {1, 1, 1, 3, 5}
Output: 4 1
Explanation: For 1st query: Segment from A1 -> {2, 3, 4} Segment from A2 -> {1, 2, 3} Possible pairs(i, j) expressed in terms of (arr[i], arr[j]) will be: (2, 1), (3, 1), (4, 2), (4, 3) . Let’s check for (4, 3) -> 4^3 = 7 binary representation will be 111, and it has a kth bit(2nd bit) from the end set. For 2nd query: Only pair will be (1,4)Input: N = 1, A1[] = {3}, A2[] = {1}, Q = 1, query[][] = {{2, 1, 1, 1, 1}}
Output: 1
Explanation: Only pair in terms of (arr[i],arr[j]) will be (3,1) -> 3^1 = 2, which has 2nd bit set from the last.
Approach: This can be solved with the following idea :
Using bits manipulation, we can find whether for each element present in the two arrays which bit is set or not and storing it in dp.
Below are the steps involved:
- initialize two dp’s for storing how many bits are being set for each ith position i.e. from 0 to 31.
- For the bit to be set, ( A[j] & 1 << i) has to be 1.
- If it is 1, we can increase the sum.
- While iterating in the query, we can find how many bits are sets or not through dp.
- To XOR to be 1 we can multiply with number of set bits and number of unset bits.
Below is the implementation of the code:
C++
// C++ code for the above approach: #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to calculate number // of pairs possible vector< long long int > xorPairs( int N, vector< int >& A1, vector< int >& A2, int Q, vector<vector< int > >& query) { vector< long long int > v; // Declarations of 2 dp's vector<vector< long long > > dp1( 31, vector< long long >(N + 1, 0)); vector<vector< long long > > dp2( 31, vector< long long >(N + 1, 0)); int i = 0; // Iterate in 30 bits while (i <= 30) { int j = 0; int sum1 = 0; int sum2 = 0; // Iterate in array while (j < N) { int curr = A1[j]; int x = 1 << i; if (x & curr) { sum1++; } dp1[i][j] = sum1; curr = A2[j]; x = 1 << i; if (x & curr) { sum2++; } dp2[i][j] = sum2; j++; } i++; } i = 0; // Iterate in queries while (i < query.size()) { // Assinging values to variable int k = query[i][0] - 1; int l1 = query[i][1] - 1; int r1 = query[i][2] - 1; int l2 = query[i][3] - 1; int r2 = query[i][4] - 1; long long s1 = 0; long long u1 = 0; // Calculation of upper and lower bits long long lower = 0; long long upper = 0; if (l1 != 0) { lower = dp1[k][l1 - 1]; } upper = dp1[k][r1]; s1 = upper - lower; u1 = r1 - l1 + 1 - s1; lower = 0; long long s2 = 0; long long u2 = 0; if (l2 != 0) { lower = dp2[k][l2 - 1]; } upper = dp2[k][r2]; s2 = upper - lower; u2 = r2 - l2 + 1 - s2; // Number of pairs possible long long sum = 0; // Counting of 0 and 1's accordingly sum += (s2 * 1ll * u1); sum += (s1 * 1ll * u2); // Add it to vector v.push_back(sum); i++; } return v; } // Driver code int main() { int N = 1; vector< int > A1 = { 3 }; vector< int > A2 = { 1 }; int Q = 1; vector<vector< int > > query = { { 2, 1, 1, 1, 1 } }; // Function call vector< long long int > res = xorPairs(N, A1, A2, Q, query); // Print the answer for ( auto a : res) { cout << a << " "; } return 0; } |
Java
import java.util.ArrayList; import java.util.List; class Main { // Function to calculate the number of pairs possible public static List<Long> xorPairs( int N, List<Integer> A1, List<Integer> A2, int Q, List<List<Integer>> query) { List<Long> v = new ArrayList<>(); // Declarations of 2 dp's List<List<Long>> dp1 = new ArrayList<>(); List<List<Long>> dp2 = new ArrayList<>(); for ( int i = 0 ; i <= 30 ; i++) { dp1.add( new ArrayList<>()); dp2.add( new ArrayList<>()); for ( int j = 0 ; j <= N; j++) { dp1.get(i).add(0L); dp2.get(i).add(0L); } } int i = 0 ; // Iterate in 30 bits while (i <= 30 ) { int j = 0 ; int sum1 = 0 ; int sum2 = 0 ; // Iterate in array while (j < N) { int curr = A1.get(j); int x = 1 << i; if ((x & curr) != 0 ) { sum1++; } dp1.get(i).set(j, ( long ) sum1); curr = A2.get(j); x = 1 << i; if ((x & curr) != 0 ) { sum2++; } dp2.get(i).set(j, ( long ) sum2); j++; } i++; } i = 0 ; // Iterate in queries while (i < query.size()) { // Assinging values to variable int k = query.get(i).get( 0 ) - 1 ; int l1 = query.get(i).get( 1 ) - 1 ; int r1 = query.get(i).get( 2 ) - 1 ; int l2 = query.get(i).get( 3 ) - 1 ; int r2 = query.get(i).get( 4 ) - 1 ; long s1 = 0 ; long u1 = 0 ; // Calculation of upper and lower bits long lower = 0 ; long upper = 0 ; if (l1 != 0 ) { lower = dp1.get(k).get(l1 - 1 ); } upper = dp1.get(k).get(r1); s1 = upper - lower; u1 = r1 - l1 + 1 - s1; lower = 0 ; long s2 = 0 ; long u2 = 0 ; if (l2 != 0 ) { lower = dp2.get(k).get(l2 - 1 ); } upper = dp2.get(k).get(r2); s2 = upper - lower; u2 = r2 - l2 + 1 - s2; // Number of pairs possible long sum = 0 ; // Counting of 0 and 1's accordingly sum += (s2 * 1L * u1); sum += (s1 * 1L * u2); // Add it to the list v.add(sum); i++; } return v; } public static void main(String[] args) { int N = 1 ; List<Integer> A1 = List.of( 3 ); List<Integer> A2 = List.of( 1 ); int Q = 1 ; List<List<Integer>> query = List.of(List.of( 2 , 1 , 1 , 1 , 1 )); // Function call List<Long> res = xorPairs(N, A1, A2, Q, query); // Print the answer for ( long a : res) { System.out.print(a + " " ); } } } |
Python3
# Python code for the above approach : def xorPairs(N, A1, A2, Q, query): v = [] # Declarations of 2 dp's dp1 = [[ 0 ] * (N + 1 ) for _ in range ( 31 )] dp2 = [[ 0 ] * (N + 1 ) for _ in range ( 31 )] i = 0 # Iterate in 30 bits while i < = 30 : j = 0 sum1 = 0 sum2 = 0 # Iterate in array while j < N: curr = A1[j] x = 1 << i if x & curr: sum1 + = 1 dp1[i][j] = sum1 curr = A2[j] x = 1 << i if x & curr: sum2 + = 1 dp2[i][j] = sum2 j + = 1 i + = 1 i = 0 # Iterate in queries while i < len (query): # Assigning values to variables k = query[i][ 0 ] - 1 l1 = query[i][ 1 ] - 1 r1 = query[i][ 2 ] - 1 l2 = query[i][ 3 ] - 1 r2 = query[i][ 4 ] - 1 s1 = 0 u1 = 0 # Calculation of upper and lower bits lower = 0 upper = 0 if l1 ! = 0 : lower = dp1[k][l1 - 1 ] upper = dp1[k][r1] s1 = upper - lower u1 = r1 - l1 + 1 - s1 lower = 0 s2 = 0 u2 = 0 if l2 ! = 0 : lower = dp2[k][l2 - 1 ] upper = dp2[k][r2] s2 = upper - lower u2 = r2 - l2 + 1 - s2 # Number of pairs possible summation = 0 # Counting of 0 and 1's accordingly summation + = s2 * 1 * u1 summation + = s1 * 1 * u2 # Add it to the vector v.append(summation) i + = 1 return v # Driver code if __name__ = = "__main__" : N = 1 A1 = [ 3 ] A2 = [ 1 ] Q = 1 query = [[ 2 , 1 , 1 , 1 , 1 ]] # Function call res = xorPairs(N, A1, A2, Q, query) # Print the answer for a in res: print (a, end = " " ) |
C#
// C# Implementation using System; using System.Collections.Generic; class MainClass { // Function to calculate the number of pairs possible public static List< long > XorPairs( int N, List< int > A1, List< int > A2, int Q, List<List< int >> query) { List< long > v = new List< long >(); // Declarations of 2 dp's List<List< long >> dp1 = new List<List< long >>(); List<List< long >> dp2 = new List<List< long >>(); for ( int i = 0; i <= 30; i++) { dp1.Add( new List< long >()); dp2.Add( new List< long >()); for ( int j = 0; j <= N; j++) { dp1[i].Add(0L); dp2[i].Add(0L); } } int bitIndex = 0; // Change variable name to bitIndex // Iterate in 30 bits while (bitIndex <= 30) { int j = 0; int sum1 = 0; int sum2 = 0; // Iterate in array while (j < N) { int curr = A1[j]; int x = 1 << bitIndex; if ((x & curr) != 0) { sum1++; } dp1[bitIndex][j] = ( long )sum1; curr = A2[j]; x = 1 << bitIndex; if ((x & curr) != 0) { sum2++; } dp2[bitIndex][j] = ( long )sum2; j++; } bitIndex++; } bitIndex = 0; // Iterate in queries while (bitIndex < query.Count) { // Assinging values to variable int k = query[bitIndex][0] - 1; int l1 = query[bitIndex][1] - 1; int r1 = query[bitIndex][2] - 1; int l2 = query[bitIndex][3] - 1; int r2 = query[bitIndex][4] - 1; long s1 = 0; long u1 = 0; // Calculation of upper and lower bits long lower = 0; long upper = 0; if (l1 != 0) { lower = dp1[k][l1 - 1]; } upper = dp1[k][r1]; s1 = upper - lower; u1 = r1 - l1 + 1 - s1; lower = 0; long s2 = 0; long u2 = 0; if (l2 != 0) { lower = dp2[k][l2 - 1]; } upper = dp2[k][r2]; s2 = upper - lower; u2 = r2 - l2 + 1 - s2; // Number of pairs possible long sum = 0; // Counting of 0 and 1's accordingly sum += (s2 * 1L * u1); sum += (s1 * 1L * u2); // Add it to the list v.Add(sum); bitIndex++; } return v; } public static void Main( string [] args) { int N = 1; List< int > A1 = new List< int >{ 3 }; List< int > A2 = new List< int >{ 1 }; int Q = 1; List<List< int >> query = new List<List< int >>{ new List< int >{ 2, 1, 1, 1, 1 } }; // Function call List< long > res = XorPairs(N, A1, A2, Q, query); // Print the answer foreach ( long a in res) { Console.Write(a + " " ); } } } // This code is contributed by Sakshi |
Javascript
// JavaScript Code function xorPairs(N, A1, A2, Q, query) { let v = []; // Declarations of 2 dp's let dp1 = []; let dp2 = []; for (let i = 0; i <= 30; i++) { dp1.push(Array(N + 1).fill(0)); dp2.push(Array(N + 1).fill(0)); } let i = 0; // Iterate in 30 bits while (i <= 30) { let j = 0; let sum1 = 0; let sum2 = 0; // Iterate in array while (j < N) { let curr = A1[j]; let x = 1 << i; if ((x & curr) !== 0) { sum1++; } dp1[i][j] = sum1; curr = A2[j]; x = 1 << i; if ((x & curr) !== 0) { sum2++; } dp2[i][j] = sum2; j++; } i++; } i = 0; // Iterate in queries while (i < query.length) { // Assinging values to variable let k = query[i][0] - 1; let l1 = query[i][1] - 1; let r1 = query[i][2] - 1; let l2 = query[i][3] - 1; let r2 = query[i][4] - 1; let s1 = 0; let u1 = 0; // Calculation of upper and lower bits let lower = 0; let upper = 0; if (l1 !== 0) { lower = dp1[k][l1 - 1]; } upper = dp1[k][r1]; s1 = upper - lower; u1 = r1 - l1 + 1 - s1; lower = 0; let s2 = 0; let u2 = 0; if (l2 !== 0) { lower = dp2[k][l2 - 1]; } upper = dp2[k][r2]; s2 = upper - lower; u2 = r2 - l2 + 1 - s2; // Number of pairs possible let sum = 0; // Counting of 0 and 1's accordingly sum += s2 * u1; sum += s1 * u2; // Add it to the list v.push(sum); i++; } return v; } // Test case let N = 1; let A1 = [3]; let A2 = [1]; let Q = 1; let query = [[2, 1, 1, 1, 1]]; // Function call let res = xorPairs(N, A1, A2, Q, query); // Print the answer console.log(res.join( ' ' )); |
1
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us