Monday, July 20, 2015

XOR of all sub arrays

Given an array of elements, how do we find the XOR of each sub-array and XOR of those results?

For example let us consider the array [1, 2, 3], all possible sub-arrays are

XOR[1] = 1
XOR[1, 2] = 1 ^ 2 = 3
XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0
XOR[2] = 2
XOR[2, 3] = 2 ^ 3 = 1
XOR[3] = 3

And the result XOR[1, 3, 0, 2, 1, 3] = 2.

Brute force solution:
From the above example, you can see that an array of 3 elements has 6 sub-arrays. Similarly you can verify the count by listing the sub-arrays for N= 4 and N= 5. In general, for an array of N elements there will be N*(N+1)/2 sub-arrays. We have to calculate the XOR of each of these sub arrays. So an outline of algorithm can be as follows.

for i in range(1,N)
   for j in range(i,N)
      for k in range(i,j)
         x = XOR(x,A[k])

This is clearly not en efficient solution and take O(n3) time. We can also use dynamic programming to pre-calculate the XOR values so that time can be reduced to O(n2). But is there any better method?

Efficient Solution:
Observe how many times, each element appear in all the sub arrays. In the above example
1 - 3 times
2 - 4 times
3 - 3 times

Consider 0-index, in general A[i] appears (N-i)*(i+1) times. 

We also know that if an element is XOR'ed with itself even number of times, it is zeroed out. and if it is odd number of times, it remains the same. For example

V ^ V ^ V ^ V = 0
V ^ V ^ V = V

Consider the two cases when the number of elements N is Even or Odd
N is even, each element appear even number of times:

N= 2, 
A[0] - 2 times
A[1] - 2 times
N = 4,
A[0] - 4 times
A[1] - 6 times
A[2] - 6 times
A[3] - 4 times

This is because either (N-i) or (i+1) is always even for all values of i.
Hence, for an array of even length, the XOR of all sub-array becomes Zero.

N is odd, the elements at even index will only prevail in the final result.

The following C++ program implements the above approach. The time complexity of this algorithm is O(n).

Thursday, July 16, 2015

Character to be removed to become a palindrome

Given a string, We have to find out by removing which character, it becomes a palindrome.

For example consider the string "racercar", the character 'r' at index 4 should be removed to become a palindrome.

The approach here is simple.

Start from both ends of the string and compare both characters. If they are equal, we increment the front index and decrement the back index. If they are not equal, one of the characters needs to be removed. We can check this by verifying if a palindrome can be formed by removing the front character or the back character. Repeat the above procedure until both indices meet each other.

We are printing the index of the character to be removed. If the string is already a palindrome, we print -1.

This solution has O(n) time complexity.

Here are the implementations in C++ and Python.