Monday, June 30, 2014

Minimum AND of all subsets

This problem is from a recent contest on Hackerrank. If you want to solve this problem on your own, Click on this link.

Here is the problem statement:

Given array of size N, we have to find all the subsets of size > 2 of this array. Apply AND (bitwise &) on all the subsets. Print the minimum among those numbers.

For example let us consider the array {2, 8, 13, 7}, the minimum AND of any subset of size > 2 is 0 for subset {7,8}

0111
1000
----&
0000

At first look, this problem looks like combinations problem. This solution tries to generate all the subsets of given array and find the minimum of all of them. This solution is of exponential time complexity and prohibitively expensive for larger inputs. But there is a trick to solve this problem.

Suppose that there exists some numbers whose AND is the minimum value among all the subsets. If we add any number of elements to this set, we get the same result. In the above example if add any element to {7,8} the result is no less than zero.

So the solution is to simply AND all the elements of the array!

Here is the Java solution.