Wednesday, July 30, 2014

Number of rectangles

Given a number of unit squares (1 x 1). How many different rectangles can be formed with them?

For example let us consider 4 units. We can form 5 different rectangles like the following. Two rectangles are considered same if they are oriented in a different way but same dimensions.


Basically we have to arrange 1 to N-1 units to form rectangles of different dimensions.
This boils down to finding the sum of the number of pairs factors of 1 to N numbers.

Here is the C++ program to do that.

Friday, July 25, 2014

Finding the number of duplicates in a list of numbers

Given a list of numbers, we have to find how many duplicate entries are present in it?

For example consider the list of numbers {5, 1, 9, 5, 2, 1, 6, 4, 5, 8}
It has 3 duplicate numbers.

There are many ways to do this. In this post, I present one of the simplest ways using C++ STL set data structure, and Java HashSet data structure
 

The insert() method of the set returns a pair of type 
pair< set<type>::iterator, bool >
 

The second value in the pair is true if a new element is inserted. It is false if there is already an existing element.

The add() method of HashSet returns true if new element is inserted, and false if no new element is inserted(duplicate)

We can make use of this property to count the number of duplicate elements.

Here is the simple C++ implementation.


Here is the Java Implementation.

Thursday, July 24, 2014

Adding a list of big numbers

Most of the popular programming languages like C/C++, Java, C# provide primitive data types (int, long) to hold values up to only a specific range.

A 64-bit integer can store only store numbers in the range of -264 to 263-1. This can store numbers containing roughly 19-20 digits.
What if we have to deal with even bigger numbers.

For example, numbers such as 1298372305835723862093487348

We have to implement our own methods to do arithmetic on such numbers. Just like the following we do for addition.


  7 8 2 9 3 4 3
  3 4 5 6 9 8 1
  1 7 6 5 2 3 5
  2 1 2 1 1 0  ---->carry
----------------
1 3 0 5 1 5 5 9

In this post we will see how can we implement addition of a list of big numbers. C++ does not have a standard library data structure/algorithms to do so. How ever Java provides a BigInteger class for this purpose.

We assume that these big numbers are represented as strings.

Here is how it is implemented in C++.

Here is how it is implemented in Java. See how BigInteger made our life easier!

Tuesday, July 22, 2014

Number of trailing zeros in a factorial

This problem looks easy to solve for small numbers. Simply calculate the factorial and count how many zeroes are present at the end!

But the factorial grows big very fast even for small numbers which cannot fit into standard data types. (20! = 2432902008176640000. Cannot fit into a long variable also). In summary this is not the best approach that one can think of.

We can use some simple mathematical properties to solve this problem easily and efficiently. 

Can you think how can a factorial value gets a zero at the end?

If two numbers, one, a multiple 5 and and the other a multiple of 2 are multiplied, it contributes a zero at the end in the product.


For example 2*5, 14*15, 26*25 etc...
 

So our job is to calculate number of such pairs. Since the multiples of 2 will always be greater than multiples of 5, We can simply count 5-multiples which divide the given number. This is simply (number/5)

But the problem is not yet over!
How many zeroes does a 25 contribute?
Let us consider 26! = 1 * 2 * ...5 * 6...*25*26

It can be re written as 
1 * 2 *...* 23 * (12* 2) * (5 * 5) * (2 * 13)
 

It contributes to two zeroes!

Similarly we can observe that 125 contributes to 3 zeroes and so on...
 

So as a conclusion, the result is the sum of 5 multiples, 25 multiples, 125 multiples etc... which are also divisors of the given number.

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

Friday, July 18, 2014

Permutation cycles - Code chef problem

This is a problem from CodeChef. Follow this link if you want to try this problem on your own.

Given a permutation of numbers from 1 to N. You can walk through the permutation to find cycles in it.
Here is how you can do it. Consider the permutation {3, 5, 2, 1, 4, 6}

Start with the first number at index 1, it contains 3.
Go to index 3, it contains 2.
Go to index 2, it contains 5.
Go to index 5, it contains 4.
Go to index 4, it contains 1.
Here we come back to index 1 again. This completes a cycle {1,3,2,5,4,1}
And if we start with 6, we end up there itself. This is a one element cycle {6,6}.

Similarly the permutation {3,2,1,5,4,6} contains 4 such cycles
1 3 1
2 2
4 5 4
6 6


The problem is given a permutation as input, you have to print the number of cycles and the cycles also.
 
To solve this problem we can maintain a visited array to store whether the element is already explored or not. Run a loop until you find a unvisited element, and start walking to find the cycle.
This is a purely an implementation challenge and does not need any algorithmic thinking.

Here is the simple C++ implementation.

Tuesday, July 15, 2014

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).

Wednesday, July 2, 2014

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.

Tuesday, July 1, 2014

A simple problem pattern in competitive programming

Consider the following two problems appeared in two different competitions, which underlies the same pattern.
Given a number of chocolates (N). For each of M wrappers, we will get a chocolate free. How can one have the maximum number of chocolates by following an optimum strategy?
Given a number of candles (N) each of them burn for 1 hours. Assume that from the remaining wax of M burning candles we can make another candle. What is the maximum number of hours for which we can lit the candles by following the optimum strategy?

The solution is simple. As long as we have more chocolates than M, we continue to eat them and produce N/M wrappers which again fetch some more chocolates. Add it to the remaining chocolates and repeat this procedure until we have less number of chocolates than
M.

Following is the simple C++ program which implements the above algorithm.