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.

Friday, June 20, 2014

Stamps problem - SPOJ

This problem is from SPOJ. Give it a try by following this link!

The simplified problem statement is as follows. 


You need to collect some stamps from friends. Suppose you have n friends and each of them have some stamps with them {s1, s2, ... sn}.
 
The problem is to find if we can collect the targeted number of stamps. If it is possible, we have to find the minimum number of friends to collect the stamps from.

For example. Let us assume we have a target of 100 stamps, and we have 5 friends with {27, 68, 39, 4, 51} stamps.
We just need to collect from 2 friends to achieve the target {68,51}.

The solution is simple.
  • First check the sum of stamps from all the friends is sufficient to reach the target.
  • If it is possible just sort the friends in descending order of the number of stamps they have.
  • Keep collecting the stamps from them until have just enough stamps to reach the target.
Here is the C++ implementation of the above algorithm.

Thursday, June 19, 2014

Boys and Girls - SPOJ problem

This problem is from SPOJ. Please follow this link if you want to try on your own!

The problem is as follows.

Given some number of boys and girls, we have to arrange them in a row such that the same gender appear together is minimized.
 
We have to find the minimum number of any gender appear together in any arrangement.

For example
Given that there are 3 boys and 3 girls, we can arrange them alternatively B G B G B G. So the minimum number is 1
If there are 4 boys and 1 girl, we can arrange them like B B G B B, so the minimum number is 2.

Solution approach:

The solution is very simple. We have to divide the bigger number by smaller number plus 1. 

Consider that there are N boys and M girls (N > M). The optimal way of arranging them is to put one girl between a group of (N/M+1) boys.

Here is the C++ code.

Wednesday, June 18, 2014

Birthday candles - Codechef problem

This is from CodeChef practice problems. Follow this link to try on your own!

Here is the simplified problem statement.

A number of candles are given each of them labelled with the digit 0-9. We have to find the minimum positive number that can not be formed with the given candles. 

The input is given as an array of size 10.
Array[0] indicates the number of '0' candles
Array[1] indicates the number of '1' candles and so on upto Array[9].

For example:
  • For input 1 6 2 1 1 2 1 1 2 0, the output is 9. Since we have zero '9' candles, the minimum number that can not be formed is 9.
  • For input 2 3 2 2 1 2 1 1 1 1, the output is 44; because we have only one '4' candle.
  • For input 0 1 1 1 1 1 1 1 1 1, the output is 10;  We have one '1' candle so we can not form 10 with the given candles.
Note: Even though we don't have any '0' candles, the minimum number is not 0 because the answer should be a positive number.

Here is the approach to solve this problem.
  • Identify the left most digit with minimum count. It can be '0' also.
  • Form a number by repeating the minimum digit  (count+1) times
  • A special case occurs when '0' candle has minimum count, we have to prefix '1' to it, as we can not have all zeros.
  • One more special case is when 0 and some other digit has the same minimum count, we have to consider the left most non-zero digit. Take a look at the following case to understand the situation. 
    • 2  3  4   7  6  2  8  3  5  9
    • Both '0' and '5' has the count of 2. If we consider zero, the output becomes 1000 according to the above algorithm. If we consider '5', the output becomes 555. Since 555 < 1000; the answer should be 555.
Here is the C++ code for this problem.

Tuesday, June 10, 2014

Continuous sequence

This problem is from codeforces. If you want to solve this problem on your own. Please head over here and solve it!

The simplified problem statement is as follows.


Given a sequence of 0 and 1s. Check if contains a continuous sequence of 0/1 of length 7.

For example see some input output combinations

Input                             Output
------------------------------------------
10001010010011                    NO
1000000001100                     YES
000111111111110                   YES

Your program should accept a sequence of 0, 1s as input and print YES of there is a sequence of 7 0/1s in it or NO if does not contain such a sequence.


The algorithm is as follows.


We maintain a state variable to see if we are getting a sequence 0s or sequence of 1s. We also use a continuity counter to track the maximum number of similar symbols. If this counter reaches 7 anytime we break and declare the result as YES.


If we finish processing the input without the counter reaching 7 anytime, we output the result as NO.

Here is the C++ implementation of the above algorithm.