Category Archives: SPOJ

Maximum number of contiguous ones with K zeros

Given an array of size N, containing only 0’s and 1’s, and a number K, what is the maximum length of the sub-array with contiguous 1’s with at most K 0’s?

For example consider the array

A = [1, 1, 0, 1, 0, 0, 1], K = 2, the maximum length is 5. i.e the sub-array A[0:4]

This problem can be solved using sliding window algorithm. Take two indexes front and back which defines a window. We keep expanding the window by incrementing the back index as long as the window contains less than or equal to K zeros. That means, at any time, the window contains at most K 0’s. If it exceeds K, we increment the front index to reduce the number of zeros to K. Continue this procedure until the back index reaches the end of the array. We also keep track of the largest window during this process.

This algorithm takes O(n) time.

Here is the C++ code.

Problem Source: SPOJ REPROAD

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.

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.

Problem of candies: SPOJ

This problem is from SPOJ (Sphere Online Judge – A site to practice your problem solving skills). If you want to solve this problem on your own, please follow the link.

The simplified problem description is as follows. 

A teacher has n packets of candies of varying sizes. The problem is to find the number of candies to be moved from one packet to others to get equal number of candies in all packets.

For example consider 5 packets of candies having {1, 2, 3, 4, 5}  candies. the number of candies to be moved are 3.
Explanation: Take out 1 candy from 4 and add it to 2, and  take out 2 from 5 and add it to 1. Now every packet contains 3 candies.

There are cases where we can not make candies in each packet equal by moving any number of candies. We have to output -1 in that case.

The approach to solve this problem is as follows. 

First check if we can equal the packets in any way. How can we do this?
Sum all numbers and see if it is properly divided by the number of candies (integer average is possible). If it is possible we can proceed to divide the candies to make them equal.

The next problem is to find out the number of candies to be moved. Find the sum of all excess candies in each packet by comparing them with average number of candies.

This algorithm runs in O(n) time and O(1) space complexity.

Here is the accepted C++ code for this problem.