Given two arrays A and B of sizes N and M respectively, the task is to calculate the XOR sum of bitwise ANDs of all pairs of A and B
Examples:
Input: A={3, 5}, B={2, 3}, N=2, M=2
Output:
0
Explanation:
The answer is (3&2)^(3&3)^(5&2)^(5&3)=1^3^0^2=0.Input: A={1, 2, 3}, B={5, 6}, N=3, M=2
Output:
0
Naive Approach: The naive approach would be to use nested loops to calculate the bitwise ANDs of all pairs and then find their XOR sum. Follow the steps below to solve the problem:
- Initialize a variable ans to -1, which will store that final answer.
- Traverse array A, and do the following:
- For each current element, traverse the array B, and do the following:
- If ans is equal to -1, store the bitwise AND of the elements in ans.
- Otherwise, store the bitwise XOR of ans and the bitwise AND of the elements in ans.
- For each current element, traverse the array B, and do the following:
- Return ans.
Below is the implementation of the above approach:
C++
// C++ algorithm for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the XOR sum of all ANDS of all// pairs on A[] and B[]int XorSum(int A[], int B[], int N, int M){ // variable to store anshu int ans = -1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // when there has been no // AND of pairs before this if (ans == -1) ans = (A[i] & B[j]); else ans ^= (A[i] & B[j]); } } return ans;}// Driver codeint main(){ // Input int A[] = { 3, 5 }; int B[] = { 2, 3 }; int N = sizeof(A) / sizeof(A[0]); int M = sizeof(B) / sizeof(B[0]); // Function call cout << XorSum(A, B, N, M) << endl;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to calculate the XOR sum of all ANDS of all// pairs on A[] and B[]public static int XorSum(int A[], int B[], int N, int M){ // variable to store anshu int ans = -1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // when there has been no // AND of pairs before this if (ans == -1) ans = (A[i] & B[j]); else ans ^= (A[i] & B[j]); } } return ans;}// Driver code public static void main (String[] args) { // Input int A[] = { 3, 5 }; int B[] = { 2, 3 }; int N = A.length; int M =B.length; // Function call System.out.println(XorSum(A, B, N, M)); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 algorithm for the above approach# Function to calculate the XOR sum of all ANDS of all# pairs on A and Bdef XorSum(A, B, N, M): # variable to store anshu ans = -1 for i in range(N): for j in range(M): # when there has been no # AND of pairs before this if (ans == -1): ans = (A[i] & B[j]) else: ans ^= (A[i] & B[j]) return ans # Driver codeif __name__ == '__main__': # Input A = [3, 5] B = [2, 3] N = len(A) M = len(B) # Function call print (XorSum(A, B, N, M))# This code is contributed by mohit kumar 29. |
C#
// C# algorithm for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to calculate the XOR sum of all ANDS of all// pairs on A[] and B[]static int XorSum(int []A, int []B, int N, int M){ // variable to store anshu int ans = -1; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { // when there has been no // AND of pairs before this if (ans == -1) ans = (A[i] & B[j]); else ans ^= (A[i] & B[j]); } } return ans;}// Driver codepublic static void Main(){ // Input] int []A = {3, 5}; int []B = {2, 3}; int N = A.Length; int M = B.Length; // Function call Console.Write(XorSum(A, B, N, M));}}// This code is contributed by SURENDER_GANGWAR. |
Javascript
<script>// JavaScript program for the above approach // Function to calculate the XOR sum of all ANDS of all // pairs on A[] and B[] function XorSum(A, B, N, M) { // variable to store anshu let ans = -1; for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { // when there has been no // AND of pairs before this if (ans == -1) ans = (A[i] & B[j]); else ans ^= (A[i] & B[j]); } } return ans; } // Driver code // Input let A = [3, 5]; let B = [2, 3]; let N = A.length; let M = B.length; // Function call document.write(XorSum(A, B, N, M)); // This code is contributed by Potta Lokesh </script> |
Output
0
Time Complexity: O(N*M)
Auxiliary Space:O(1)
Efficient Approach:
Observation: The distributive property of XOR over AND can be used to solve the problem.
let A[] = [a, b, c]
let B[] = [d, e]
Result :
(a & d) ^ (a & e) ^ (b & d) ^ (b & e) ^ (c & d) ^ (c & e)
By applying distributive property,
[(a ^ b ^ c) & d] ^ [(a ^ b ^ e) & e]
(a ^ b ^ c) & (d ^ e)
Follow the steps below to solve the problem:
- Initialize two variables ans1 and ans2 to 0, which will store the bitwise XOR sums of the first array and the second array respectively.
- Traverse A and for each current element:
- Store the bitwise XOR of ans1 and the current element in ans1.
- Traverse B and for each current element:
- Store the bitwise XOR of ans2 and the current element in ans2.
- Return ans1&ans2.
Below is the implementation of the above approach:
C++14
// C++ algorithm for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the XOR sum of all ANDS of all// pairs on A[] and B[]int XorSum(int A[], int B[], int N, int M){ // variable to store xor sums // of first array and second // array respectively. int ans1 = 0, ans2 = 0; // Xor sum of first array for (int i = 0; i < N; i++) ans1 = ans1 ^ A[i]; // Xor sum of second array for (int i = 0; i < M; i++) ans2 = ans2 ^ B[i]; // required answer return (ans1 & ans2);}// Driver codeint main(){ // Input int A[] = { 3, 5 }; int B[] = { 2, 3 }; int N = sizeof(A) / sizeof(A[0]); int M = sizeof(B) / sizeof(B[0]); // Function call cout << XorSum(A, B, N, M) << endl;} |
Java
// Java algorithm for the above approachimport java.io.*;class GFG{// Function to calculate the XOR sum of // all ANDS of all pairs on A[] and B[]static int XorSum(int A[], int B[], int N, int M){ // Variable to store xor sums // of first array and second // array respectively. int ans1 = 0, ans2 = 0; // Xor sum of first array for(int i = 0; i < N; i++) ans1 = ans1 ^ A[i]; // Xor sum of second array for(int i = 0; i < M; i++) ans2 = ans2 ^ B[i]; // Required answer return (ans1 & ans2);}// Driver codepublic static void main(String[] args){ // Input int A[] = { 3, 5 }; int B[] = { 2, 3 }; int N = A.length; int M = B.length; // Function call System.out.print(XorSum(A, B, N, M));}}// This code is contributed by subham348 |
Python3
# python 3 algorithm for the above approach# Function to calculate the XOR sum of all ANDS of all# pairs on A[] and B[]def XorSum(A, B, N, M): # variable to store xor sums # of first array and second # array respectively. ans1 = 0 ans2 = 0 # Xor sum of first array for i in range(N): ans1 = ans1 ^ A[i] # Xor sum of second array for i in range(M): ans2 = ans2 ^ B[i] # required answer return (ans1 & ans2)# Driver codeif __name__ == '__main__': # Input A = [3, 5] B = [2, 3] N = len(A) M = len(B) # Function call print(XorSum(A, B, N, M)) # This code is contributed by bgangwar59. |
C#
// C# program for the above approachusing System;class GFG {// Function to calculate the XOR sum of // all ANDS of all pairs on A[] and B[]static int XorSum(int[] A, int[] B, int N, int M){ // Variable to store xor sums // of first array and second // array respectively. int ans1 = 0, ans2 = 0; // Xor sum of first array for(int i = 0; i < N; i++) ans1 = ans1 ^ A[i]; // Xor sum of second array for(int i = 0; i < M; i++) ans2 = ans2 ^ B[i]; // Required answer return (ans1 & ans2);} // Driver code public static void Main (String[] args) { // Input int[] A = { 3, 5 }; int[] B = { 2, 3 }; int N = A.Length; int M = B.Length; // Function call Console.Write(XorSum(A, B, N, M)); }}// This code is contributed by code_hunt. |
Javascript
<script>// JavaScript algorithm for the above approach// Function to calculate the XOR sum of all ANDS of all// pairs on A[] and B[]function XorSum(A, B, N, M){ // variable to store xor sums // of first array and second // array respectively. let ans1 = 0, ans2 = 0; // Xor sum of first array for (let i = 0; i < N; i++) ans1 = ans1 ^ A[i]; // Xor sum of second array for (let i = 0; i < M; i++) ans2 = ans2 ^ B[i]; // required answer return (ans1 & ans2);}// Driver code // Input let A = [ 3, 5 ]; let B = [ 2, 3 ]; let N = A.length; let M = B.length; // Function call document.write(XorSum(A, B, N, M));</script> |
Output
0
Time Complexity: O(N+M)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
