Category Archives: Codeforces

Odd number out

Given an array of numbers which contains all even numbers except one, or all add numbers except one.
How do you find the different number?

For example consider the array [1, 2, 3, 5, 9], 2 is the different number.
Similarly in the array [10, 6, 7, 24, 36], 7 is the different number.

This problem was originally appeared on Codeforces.

This is a simple implementation problem, which can be solved in one iteration.
When we are reading numbers, just keep track of the following information.

  • first even index
  • first odd index
  • even number count

At the end, check if the even number count is 1, If it is, then print first even index, otherwise print first odd index.
Here is the C++ code for this.

Minimum area of a square enclosing given set of points

Problem:
Given a set of coordinates in a two dimensional plane, How do we find the area of a minimum square which includes all the points. The points can exist on the border also.

For example consider two points (0,0), (1,2) we need a minimum 2*2 square to cover these points. Hence the area is 4.

Similarly if the input coordinates are (-1,1), (1,3), (0,2) we need 2*2 square.

This is a problem from Codeforces. Click here to read the problem statement and solve it on your own.

Here is the solution approach. We iterate through all the points and keep track of the maximum and minimum of x and y-coordinates. Lets assume min_x is the left most x-coordinate, and max_x is the right most x-coordinate among all the points. The difference between these two gives the minimum width required.

Similarly the difference between min_y and max_y gives the minimum height required. So to accommodate all the points, we need a square of size which is the maximum of these two differences.

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

Finding a sub list with least max-min difference – Codeforces puzzle

This is a problem from Codeforces. Please follow this link to solve this problem on your own.

The abridged problem statement is as follows.

You are given an list of numbers, and sub-list size as input. The challenge is to find a sub-list such that the difference between the maximum and minimum numbers in that sub-list is minimized.

For example consider the numbers {36, 6, 12, 42, 24, 50}, and we have to find a sub-list of size 4. By choosing {36, 42, 24, 50}, we can have a least difference of 26 i.e 50-24.

The solution is to first sort the numbers in ascending order, and move a sliding window of sub-list size from begin to end while keeping track of the minimum difference between first and last numbers of the sub-list.

Tracing with the above example, after sorting the list becomes {6, 12, 24, 36, 42, 50}
We start with 6, 36, the difference is 30
move on to 12, 42, the difference is 30
move on to 24, 50, the difference is 26
So the minimum difference is 26.

This algorithm runs in O(n*log n) time because we have to sort the list. the actual algorithm takes O(n), linear time.

Here is the C++ code for the same.

Next Round – A problem from Codeforces

This problem is from Codeforces. If you want to solve this problem on your own, follow this link.

Here is the simplified problem statement.

Given a list of scores of contestants in a competition, arranged in decreasing order. We have to calculate the number of people qualified for the next round.
This is determined as follows, consider the score at a given index, Whoever scored more than this score, qualifies for the next round as long as they have a score of greater than zero.

For example, let us consider the scores {10, 9, 8, 7, 7, 7, 5, 5} and the index (starts from 1) to take as bench mark is 5. we have a total of 6 candidates who qualify for next round.


If the scores are {0,0,0,0} and the index is 2, no one qualifies for the next round because none of them have a score greater than zero.
 
In case of {1, 0, 0, 0} and index 2, we have one candidate qualifying for the next round.

Let us look at the way of solving this problem. We have to handle two cases here.

Case 1: score[index] > 0
    In this case, we have to find the right most occurrence of the cutoff, which will give the required answer


Case 2: score[index[ <= 0
    In this case, we have to find the left most occurrence of zero, and count the remaining elements from the beginning.

Here is the C++ implementation of the above. Since finding the left most and right most elements in a sorted array can be found using binary search, the time complexity of this solution is O(log n).

Inverse permutation problem

This problem is from code forces. If you want to try this problem, follow this link.
Here is the simplified problem statement.
Given a group of N friends, each one has given a gift to other friend or themselves. An input array is given which indicates from whom each one has received their gifts. We have to print an array which shows to whom each one has given their gifts.

For example,
 
Let us consider a group of 5 friends. The input array {3, 1, 5, 2, 4} indicates that the ‘1’ has received the gift from ‘3’, and ‘2’ has received the gift from ‘1’, and so on…

The output should be {2, 4, 1, 5, 3}. This indicates that 1 has given gift to 2, 2 has given gift to 4, and so on…

This problem of finding the inverse permutation of a given sequence. The solution is described below.

Let us allocate a separate array B for output. For each A[i], fill  B[A[i]] with i by iterating through all the elements. At the end of the iteration, B has the required answer. This method runs in O(n) time.

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

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.


Number of matching pairs

This problem is from Codeforces. If you want to solve this problem on your own. Follow the link.

Following is the abridged(simplified) problem statement for the above problem.

Given an array containing values in the range [-10,10], find out how many number of matching pairs are possible?

A pair of numbers is said to be matching if one value is negative of the other (two zeros are also considered matching pair).

Consider the following examples.
[-6, 0, 1, 6, 0, -1] contains 3 matching pairs. Indices are (0,3), (1,4), (2,5)
[0, 0, 0, -5 ,3, 5] contains 4 matching pairs. Indices are (0,1), (0,2), (1,2), (3,5)

Since the problem is to find the count of matching pairs, we can always iterate through each possible pair and get the required answer. But this solution has a time complexity of O(n2).

        long long result = 0;
for( i = 0; i < n-1 ; i++ )
{
for( j = i+1; j < n; j++ )
{
if(input[i] == -input[j])
result
++;
}
}
cout
<< result << endl;


Let us look at more efficient solution. Since the given values are in specific range, we can store the frequencies of each number in an array of 21 values ( the size of the range [-10,10] ).

Count(-10) will be stored at index 0
Count(-9) will be stored at index 1

Count(0) will be stored at index 10

Count(10) will be stored at index 20

Now, the number of matching pairs is the sum of Count(-x) * Count(x) for 1<=x<=10

The number of possible pairs for n zeros is n*(n-1)/2

Below is the implementation of this algorithm in C++.