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 xoring two strings takes O(1) time. Give a divide-and-conquer algorithm to check if theres 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 should run in O(n log(n)) time.

[We expect that your algorithm is written in pseudocode, together with an English de- scription and a short, informal argument for its correctness and running time.] Note: 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.

WILL UPVOTE UPON GOOD AND DETAILED ANSWER!!!