The XOR operation between two numbers P and Q can be looked in a different way as the bitwise sum modulo 2 on the bits of P and Q. Consider P = 10010 and Q = 00110.
XOR of P and Q
Starting from leftmost, we verify the above statement :
- (1 + 0) % 2 = 1
- (0 + 0) % 2 = 0
- (0 + 1) % 2 = 1
- (1 + 1) % 2 = 0
- (0 + 0) % 2 = 0
A binary number is in the form of a ℤ2d vector where d is the number of bits in the binary number and 2 represents the allowed integer values in the vector viz., {0, 1}. So, the result of a XOR operation between two numbers P and Q is the vector addition mod 2 of two ℤ2d vectors P and Q.
P + Q = P ⊕ Q
For subtracting Q, XOR with Q on RHS to obtain P on RHS,
P = P ⊕ Q ⊕ Q
P = P
Now, given an array A of N non-negative integers, we need to find the Basis B for the elements of the array when represented as ℤ2d vectors in form of a bitmask.
Some points to note –
- The size of the basis B for a d-dimensional Vector Space can not exceed d.
- The basis vectors are independent, i.e., none of them can be expressed as a linear combination of a subset of basis vectors (other than the vector itself).
The algorithm goes as follows:
- Assume we have the basis for all the vectors till index ‘i‘ (i < N) and we need to check if A[i + 1] can be represented as a linear combination of current basis vectors.
- If not so, then add A[i + 1] to our basis, otherwise increment the index. We can effectively check this if we have all our basis vectors differ by the first set bit index (from left), let’s denote it by msb(B[j]).
- Start checking from the left bits, if index ‘s’ is set in current value of A[i + 1] and there is no basis vector with msb(B[j]) = s, then no linear combination of the existing basis vectors can represent current value of A[i + 1].
- So, insert current value of A[i + 1] in the basis.
- Otherwise, subtract B[j] with msb = s from A[i + 1] by XORing with B[j] and continue with other bits.
- If at end A[i + 1] is a null vector, then it can be represented as linear combination of the current basis vectors, otherwise not and has to be inserted in the basis.
Examples:
Input: N = 5, A = {2, 5, 11, 9, 20}
Output: {5, 2, 12, 24}
Explanation: Given input = 2(00010), 5(00101), 11(01011), 9(01001), 20(10100)
and basis = {0, 0, 0, 0, 0}, considering d = 5(for simplicity)
For i = 0, A[i] = 2(00010), first set bit is 1st bit, basis[1] = 0,
So basis becomes {0, 2, 0, 0, 0}
For i = 1, A[i] = 5(00101), first set bit is 0th bit, basis[0] = 0,
So basis becomes {5, 2, 0, 0, 0}
For i = 2, A[i] = 11(01011), first set bit is 0th bit, basis[0] = 5,
So A[i] = 11 ^ 5 = 14(01110)
Now A[i] = 14(01110), first set bit is 1st bit, basis[1] = 2,
So A[i] = 14 ^ 2 = 12(01100)
Now A[i] = 12(01100), first set bit is 2nd, basis[2] = 0,
So basis becomes {5, 2, 12, 0, 0}
For i = 3, A[i] = 9(01001), first set bit is 0th bit, basis[0] = 5,
So A[i] = 9 ^ 5 = 12(01100)
Now A[i] = 12(01100), first set bit is 2nd bit, basis[2] = 12,
So A[i] = 12 ^ 12 = 0(00000)
For i = 4, A[i] = 20(10100), first set bit is 2nd bit, basis[2] = 12,
So A[i] = 20 ^ 12 = 24(11000)
Now A[i] = 24(11000), first set bit is 3rd, basis[3] = 0,
So basis becomes {5, 2, 12, 24, 0}
So XOR Basis is {5, 2, 12, 24}Input: N = 7, A = {5, 16, 7, 18, 34, 24, 9}
Output: {5, 2, 12, 24, 16, 32}
Below is the implementation of the above approach
C++
// C++ code to implement above algorithm#include <bits/stdc++.h>using namespace std;// change d based on dimension of your vector#define d 20// Basis vector corresponding to each first 1-bitvector<int> Basis(d, 0);// Function to get the basis vectorsvoid add(int mask){ for (int i = 0; i < d; i++) { if (mask & (1 << i)) { // If the current value of mask // has first set bit at i if (Basis[i] == 0) { // If no basis vector exists // with first set bit at i Basis[i] = mask; return; } // Subtracting Basis[i] from the mask mask ^= Basis[i]; } } return;}// Driver codeint main(){ // Number of elements in the array int N = 5; // Vector containing those N elements vector<int> A{ 2, 5, 11, 9, 20 }; for (int i = 0; i < N; i++) // Finding a Basis for // the first i + 1 elements add(A[i]); cout << "The basis vectors are: \n"; for (int i = 0; i < d; i++) { if (Basis[i]) // Checking for each msb, a // non-zero basis vector cout << Basis[i] << endl; } return 0;} |
Java
// Java code to implement the above approachimport java.util.*;class GFG { // change d based on dimension of your vector static int d = 20; // Basis vector corresponding to each first 1-bit static int[] Basis = new int[d]; // Function to get the basis vectors static void add(int mask) { for (int i = 0; i < d; i++) { if ((mask & (1 << i)) != 0) { // If the current value of mask // has first set bit at i if (Basis[i] == 0) { // If no basis vector exists // with first set bit at i Basis[i] = mask; return; } // Subtracting Basis[i] from the mask mask ^= Basis[i]; } } return; } // Driver code public static void main(String[] args) { // Number of elements in the array int N = 5; // Vector containing those N elements int[] A = { 2, 5, 11, 9, 20 }; for (int i = 0; i < d; i++) { Basis[i] = 0; } for (int i = 0; i < N; i++) // Finding a Basis for // the first i + 1 elements add(A[i]); System.out.print("The basis vectors are: \n"); for (int i = 0; i < d; i++) { if (Basis[i] != 0) // Checking for each msb, a // non-zero basis vector System.out.println(Basis[i] ); } }}// This code is contributed by phasing17 |
Python3
# Function to check if it is possible to# change d based on dimension of your vectord = 20# Basis vector corresponding to each first 1-bitBasis = [0] * d# Function to get the basis vectorsdef add(mask) : for i in range(d): if (mask & (1 << i)) : # If the current value of mask # has first set bit at i if (Basis[i] == 0) : # If no basis vector exists # with first set bit at i Basis[i] = mask return # Subtracting Basis[i] from the mask mask ^= Basis[i] return# Driver codeif __name__ == "__main__": # Number of elements in the array N = 5 # Vector containing those N elements A = [ 2, 5, 11, 9, 20 ] for i in range(N): # Finding a Basis for # the first i + 1 elements add(A[i]) print("The basis vectors are: ") for i in range(d): if (Basis[i]) : # Checking for each msb, a # non-zero basis vector print(Basis[i]) # This code is contributed by code_hunt. |
C#
// C# code to implement the above approachusing System;class GFG {// change d based on dimension of your vectorstatic int d = 20;// Basis vector corresponding to each first 1-bitstatic int[] Basis = new int[d];// Function to get the basis vectorsstatic void add(int mask){ for (int i = 0; i < d; i++) { if ((mask & (1 << i)) != 0) { // If the current value of mask // has first set bit at i if (Basis[i] == 0) { // If no basis vector exists // with first set bit at i Basis[i] = mask; return; } // Subtracting Basis[i] from the mask mask ^= Basis[i]; } } return;}// Driver codepublic static void Main(){ // Number of elements in the array int N = 5; // Vector containing those N elements int[] A = { 2, 5, 11, 9, 20 }; for (int i = 0; i < d; i++) { Basis[i] = 0; } for (int i = 0; i < N; i++) // Finding a Basis for // the first i + 1 elements add(A[i]); Console.Write("The basis vectors are: \n"); for (int i = 0; i < d; i++) { if (Basis[i] != 0) // Checking for each msb, a // non-zero basis vector Console.WriteLine(Basis[i] ); }}}// This code is contributed by sanjoy_62. |
Javascript
// JavaScript code to implement above algorithm// change d based on dimension of your vectorconst d = 20;// Basis array corresponding to each first 1-bitlet Basis = Array(d).fill(0);// Function to get the basis arraysfunction add(mask){ for (let i = 0; i < d; i++) { if (mask & (1 << i)) { // If the current value of mask // has first set bit at i if (Basis[i] == 0) { // If no basis vector exists // with first set bit at i Basis[i] = mask; return; } // Subtracting Basis[i] from the mask mask ^= Basis[i]; } } return;}// Driver code// Number of elements in the arraylet N = 5;// Vector containing those N elementslet A = [2, 5, 11, 9, 20];for (let i = 0; i < N; i++) // Finding a Basis for // the first i + 1 elements add(A[i]);console.log("The basis vectors are: ");for (let i = 0; i < d; i++) { if (Basis[i]) // Checking for each msb, a // non-zero basis vector console.log(Basis[i]);}// This code is contributed by ishankhandelwals. |
The basis vectors are: 5 2 12 24
Time Complexity: O(N * d)
Auxiliary Space: O(d)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!