Monthly Archives: January 2016

Check if array can be divided into two parts with same XOR

Given an array of numbers, how do we check if it can be divided into two parts such that XOR values of both are same.

For example consider an array A = [1, 2, 3], it can be divided into [1, 2], and [3] because 0001 ^ 0010 = 0011

Similarly, [8, 3, 12, 7], can be divided into [8,7] and [3, 12] as 1000 ^ 0111 = 0011 ^ 1100 = 1111

This is a tricky question, where you need not actually try to divide the numbers into two sets. If any two parts of the array have the same XOR value, the XOR of all the elements will be Zero.

So we just need to check if the XOR value of all the elements is zero or not.

Facebook Hackercup 2016- Boomerang constellations problem solution

This problem is from the recently concluded Facebook Hackercup 2016 Qualification round. You can take a look at the problem statement in this link.

I am giving the abridged problem statement here. Given a set of coordinates in a 2D-plane, We have to find out the total number of pairs of lines with equal length and also share one end point.

For example, let us take the points {(0,0), (0,1), (1,0)}, there is one pair of lines, with a distance of 1. The line between (0,0),  (0,1) and the line between (0,0), (1,0).

The simplest way to solve this problem is this. Take a point (x,y) and try to calculate the distance to every other point. Maintain a map of distance to the number of other end points with that distance. This is O(n2 log n) solution.

Here is the C++ code for the same.