Bitwise XOR of a submatrix of a matrix generated from a given array
Given an array arr[] of length N, , a matrix of dimensions N * N was defined on the array arr[] where Mi, j = arri & arrj. Given four integers X, Y, S and T, the task is to find the Bitwise XOR of all the elements of the submatrix from top-left (X, Y) to bottom-right (S, T).
Examples:
Input: N = 3, A[] = {2, 3, 4}, (X, Y)=(0, 1), (S, T)=(2, 2)
Output: 5
Explanation:
Matrix defined on A is
{{(2&2), (2&3), (2&4)},
{(3&2), (3&3), (3&4)},
{(4&2), (4&3), (4&4)}}Finally, the matrix will be:
{{2, 2, 0},
{2, 3, 0},
{0, 0, 4}}
XOR value= (2^0)^(3^0)^(0^4) = 5Input: N=3, A[]={1, 2, 3}, (X, Y)=(0, 1), (S, T)=(1, 2)
Output: 1
Naive approach: The simplest approach is to generate the matrix M from the given array and calculate the Bitwise XOR of all the elements present in the given submatrix of M.
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient Approach: The idea is to use the following distributive property of the ‘XOR’ and ‘AND’ operations:
(A & B) ^ (A & C) = A & (B ^ C)
Therefore, the final XOR of the sub-matrix from top-left (X, Y) to bottom-right (S, T) can be calculated from the following equation:
Final XOR
= (XOR of row X)^(XOR of row X+1)^. . . . ^(XOR of row S)
= (AX & (AY ^. . . .^ AT)) ^ ….
. . . ^(AS & (AY^. . . .^AT))
= (AY^. . . .^AT)&(AX^. . .^AS)
- Iterate over the array from indices Y to T and compute the XOR of the elements.
- Traverse the array from indices X to S and compute the XOR of the elements.
- Finally, compute the Bitwise AND of computed XOR’s, which is equal to the Bitwise XOR of the submatrix from (X, Y) to (S, T)
Below is the implementation of the above approach:
C++
// C++ program of the // above approach #include <iostream> using namespace std; // Function to find the submatrix // XOR of the given matrix int submatrix_xor( int * A, int N, int X, int Y, int S, int T) { int left_xor = 0, i, right_xor = 0; // Calculating left xor // i.e A[Y]^A[Y+1]^. . .^A[T] for (i = Y; i <= T; i++) { left_xor ^= A[i]; } // Calculating right xor // i.e A[X]^A[X+1]^. . .^A[S] for (i = X; i <= S; i++) { right_xor ^= A[i]; } // Bitwise AND of left_xor and // right_xor gives required result return left_xor & right_xor; } // Driver Code int main() { int A[3] = { 2, 3, 4 }, X = 0, Y = 1, S = 2, T = 2, N = 3; // Printing xor of submatrix cout << submatrix_xor(A, N, X, Y, S, T); return 0; } |
Java
// Java program of the // above approach import java.io.*; class GFG{ // Function to find the submatrix // XOR of the given matrix static int submatrix_xor( int [] A, int N, int X, int Y, int S, int T) { int left_xor = 0 , i, right_xor = 0 ; // Calculating left xor // i.e A[Y]^A[Y+1]^. . .^A[T] for (i = Y; i <= T; i++) { left_xor ^= A[i]; } // Calculating right xor // i.e A[X]^A[X+1]^. . .^A[S] for (i = X; i <= S; i++) { right_xor ^= A[i]; } // Bitwise AND of left_xor and // right_xor gives required result return left_xor & right_xor; } // Driver Code public static void main (String[] args) { int [] A = { 2 , 3 , 4 }; int X = 0 , Y = 1 , S = 2 , T = 2 , N = 3 ; // Printing xor of submatrix System.out.print(submatrix_xor(A, N, X, Y, S, T)); } } // This code is contributed by code_hunt |
Python3
# Python3 program of the # above approach # Function to find the submatrix # XOR of the given matrix def submatrix_xor(A, N, X, Y, S, T): left_xor = 0 i = 0 right_xor = 0 # Calculating left xor # i.e A[Y]^A[Y+1]^. . .^A[T] for i in range (Y, T + 1 ): left_xor ^ = A[i] # Calculating right xor # i.e A[X]^A[X+1]^. . .^A[S] for i in range (X, S + 1 ): right_xor ^ = A[i] # Bitwise AND of left_xor and # right_xor gives required result return left_xor & right_xor # Driver Code if __name__ = = '__main__' : A = [ 2 , 3 , 4 ] X = 0 Y = 1 S = 2 T = 2 N = 3 # Printing xor of submatrix print (submatrix_xor(A, N, X, Y, S, T)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function to find the submatrix // XOR of the given matrix static int submatrix_xor( int [] A, int N, int X, int Y, int S, int T) { int left_xor = 0, i, right_xor = 0; // Calculating left xor // i.e A[Y]^A[Y+1]^. . .^A[T] for (i = Y; i <= T; i++) { left_xor ^= A[i]; } // Calculating right xor // i.e A[X]^A[X+1]^. . .^A[S] for (i = X; i <= S; i++) { right_xor ^= A[i]; } // Bitwise AND of left_xor and // right_xor gives required result return left_xor & right_xor; } // Driver Code public static void Main () { int [] A = { 2, 3, 4 }; int X = 0, Y = 1, S = 2, T = 2, N = 3; // Printing xor of submatrix Console.Write(submatrix_xor(A, N, X, Y, S, T)); } } // This code is contributed by code_hunt |
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the submatrix // XOR of the given matrix function submatrix_xor(A, N, X, Y, S, T) { let left_xor = 0, i, right_xor = 0; // Calculating left xor // i.e A[Y]^A[Y+1]^. . .^A[T] for (i = Y; i <= T; i++) { left_xor ^= A[i]; } // Calculating right xor // i.e A[X]^A[X+1]^. . .^A[S] for (i = X; i <= S; i++) { right_xor ^= A[i]; } // Bitwise AND of left_xor and // right_xor gives required result return left_xor & right_xor; } // Driver code let A = [ 2, 3, 4 ]; let X = 0, Y = 1, S = 2, T = 2, N = 3; // Printing xor of submatrix document.write(submatrix_xor(A, N, X, Y, S, T)); // This code is contributed by target_2. </script> |
5
Time Complexity: O(N), where N is the size of the array
Auxiliary Space: O(1)
Contact Us