Question

FIRST You are given a binary string x and an array A[1 : n] of binary strings. Assume that x and the elements of A have the same length. Let ⊕ denote the xor operator on binary strings. For example 1010 ⊕ 1101 = 0111, and 1110 ⊕ 1111 = 0001. Assume that xor’ing two strings takes O(1) time. Give a divide-and-conquer algorithm to check if there’s a subarray A[i : j] of A such that A[i] ⊕ · · · ⊕ A[j] = x. Your algorithm should return such a pair (i, j) if they exist; otherwise return (−1, −1). Your algorithm must be faster than O(n 2 ) time.

[We expect that your algorithm is written in pseudocode, together with an English description and a short, informal argument for its correctness and running time.]

Hint: If you are not familiar with the xor operator, try to think of it as the addition operator; the two operators have many similar properties. Still, the xor operator has this nice property: if you have x = a ⊕ b then x ⊕ a = b.

SECOND Implement your algorithm. A brute-force implementation will receive no credit. You must use either C, C++, Java, or Python 3, and there must be just a single file for the source code. In our pseudocode, array index starts from 1, but in most programming languages, array index starts from 0. For simplicity, in this implementation, we’ll use the latter convention, that is, your i and j must be within {0, . . . , n − 1}.

Answer 1

Algorithm for the above problem-

1. Compute the prefix xor-sum array.
2. Create a map mp in which we store the position of a prefixes and if any of the prefix is equal to X then print the range (1,i) as the answer.
3. Traverse the prefix array if x^prefix[i] is present in the map then there exits a range with xor equal to X and print the range (mp[m^prefix[i]],i) as the answer.
4. If we dont get any answer after traversing the prefix array then print (-1,-1).

The time complexity of this algorithm is O(nlogn).

C++ code for above problem-

Note- Considering binary strings as decimal number because it given that xor’ing two strings takes O(1) time.

#include<bits/stdc++.h>

using namespace std;

//prefix array and map
int prefix[1000];
map<int,int> mp;

int main() {

//input X and n->number of elements in array A
int x,n;
cin>>x>>n;

int i,j,k,l;

//input array element
for(i=1;i<=n;i++){
cin>>j;
//creating prefix array
prefix[i]=prefix[i-1]^j;
}

for(i=1;i<=n;i++){
//checking if the aubarray (0,i) has xor-sum X
if(prefix[i]==x){
cout<<"(0,"<<i-1<<")";
return 0;
}
//checking if the aubarray (mp[x^prefix[i]],i) has xor-sum X
if(mp[x^prefix[i]]!=0){
cout<<"("<<mp[x^prefix[i]]-1+1<<","<<i-1<<")";
return 0;
}
//mapping the prefix value and its position
mp[prefix[i]]=i;
}

//if the answer does not exits
cout<<"(-1,-1)";
return 0;
}
Code-

Input and Output-

If the answer helped then please upvote.And for any queries,please comment.