Category Archives: Hackerrank

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.

Counting the number of perfect squares in a given range

Given a range of numbers, how do we count the number of perfect squares?

This problem is posted on Hackerrank as part of 20/20 Hack March 2014.

If you do not want to read the solution and you want to solve the problem on your own, Click on the link. If you want to know the solution for the problem, read on…

For example, if the given range is [1,5] the number of perfect squares in this range is 2 (including the lower and upper bounds)
1= 12 and 4 = 22
 
Simple solution:
The obvious solution is to check if each number in the given range is a perfect square or not. This runs O(n) time. For a small range of numbers, this works fine. But for a big range, this takes a lot of time.

Can we improve this solution further?
 
We can improve this as follows.
 

First we find the square roots of lower bound and and upper bounds. The difference between them gives the required number.

For example consider the range [2,11]

sqrt(2) = 1.414
sqrt(11) = 3.316

If you round them off, and take the difference (3-1), it is 2 which is the required answer.

However we have to handle two special cases.

Case 1: Lower and upper bounds are same.
For example [4, 4]. In this case we have to check if the given number is a perfect square. If it is,  output 1, otherwise output 0.

Case 2: If the lower bound is a perfect square.
In this case, we have to add 1 to the diff of square roots. 

For example consider [4, 20]; rounded square roots are [2, 4]; the diff is 2. But there are 3 perfect squares in the given range (4, 9, 16).

In all the remaining cases, the number of perfect squares is the difference of the square roots.

Here is the C++ implementation for this problem.