Wednesday, August 27, 2014

Finding all Pythagorean triples in an array

Given an array of unique elements, Write a program to print all Pythagorean triples in it.
 

A Pythagorean triple is a set of three numbers such that square of one number is the sum of squares of the other two.
 

For example (3,4,5) is Pythagorean triple because 52 = 32 + 42
 

Consider the array {5, 6, 3, 10, 4, 2, 1 , 8, 7} 
It contains two Pythagorean triples (3,4,5) and (6,8,10)

An obvious solution to this problem could be examine all possible triples in the array and check if it satisfies the above property.
But this solution takes O(n3) time.

We can do better than this if we first square all the elements and sort them in descending order.


Then this problem is simplified to finding three indices in the array i,j,k such that arr[i] = arr[j]+arr[k]

The algorithm is as follows.

For each array[i] 0 <= i < n-2

     index1 <- i+1
     index2 <- n-1
            
     While index1 < index 2
                 
        If array[i] = array[index1] + array[inde2]
           Print Triple
           index1++
           index2--
        If array[i] <  array[index1] + array[inde2]
           index1++
        Otherwise
           index2--

Here is the implementation of the above in C++. It takes O(n log n) for sorting and O(n2) for the actual algorithm. So the effective time complexity for this problem is
O(n2)

Solution 2:
Alternatively you can use a Hash set to store all the square values. Then examine all possible pairs in the array to check if sum of their squares exists in the set.
This approach also takes O(n2) time but uses O(n) extra space. 
Note: The hash_set implementation is available only in Visual studio 10 compiler and above. In C++ 11 standard it is mentioned as unordered_set. If we use normal set, the time complexity will become O(n2 log n).

Tuesday, August 26, 2014

Finding the depth of n-ary tree given parent id representation

Given an a rooted n-ary tree represented as a parent id array, Write a program to find the depth of it.
 

The depth of a tree is defined as the maximum length of the path from root to any leaf node.

For example the following tree has a depth of 2 (for the path 0-2-4)

It is represented in parent id array as follows
index:    0  1  2  3  4
parent:  -1  0  0  0  2


This can be solved by first finding the depth of each node and returning the maximum among them. We can find the depth of each node by traversing the parent ids until we reach the root node. But this method takes O(n2) time if we naively calculate the depth of each node.

For example we calculate the depth of node 0 every time when we calculate the depths of it's descendants (1,2,3,4).

We need to use a simple memorization (Dynamic Programming) to store the depths of nodes already calculated.

For example if we already have the depth of 2, then the depth(4) is depth(2)+1.

This method runs in O(n) time because each node is visited exactly once. space complexity is O(n).

The following is a C++ implementation of the above DP algorithm.

Wednesday, August 20, 2014

Counting the number of inversions in a list

Given an array of numbers, how do we count the number of inversions in it?

An inversion is an ordered pair if indices (i,j) such that i < j and A[i] > A[j] .

For example consider the array {3, 2, 1, 5, 4}
The inversions are {(0,1), (0,2), (1,2), (3,4)} totaling 4.

We can always use the brute force approach of comparing all possible pairs of numbers to check if each pair is an inversion or not. This takes O(n2) time.

How do we solve this efficiently?

We can modify the merge sort procedure to count the number of inversions also!

Please check out my earlier post on Merge sort to understand how it works.

Here are the steps.
  • First count the inversions in the left part
  • Count the inversions in the right part
  • Count the inversions if they are merged using modified merge procedure
  • Adding the three counts gives the actual result 
We need to change the merge procedure to count the inversions. The merge procedure works like the following.

We have two sorted arrays to merge into another array.

{1, 3, 5, 7} + {2, 4, 6, 8} = {1, 2, 3, 4, 5, 6, 7, 8}
  • Take two pointers to start of the two arrays.
  • Compare the two elements to see which element goes to the sorted list first.
  • Increment the corresponding index.
  • Repeat the above steps until we reach the end of either of them.
  • Add the remaining elements if any.
While comparing the two elements if the left element is lesser than right element, we simply proceed.
If the right element is lesser than left elements, then it is also lesser than all elements to the right of left element. So increment the inversion counter accordingly.

For example
{.... 5, 9, 12, 15, ...}
{.....3,....}

3 Appears in the right and 5 appears in left. So we can count all the inversions (5,3), (9,3), (12,3)... in this step itself.

Here is the C++ code which implements the above algorithm. The time complexity of this implementation is O(n log n).


Friday, August 8, 2014

Maximum number of overlapping intervals

Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time.

For example let us consider the following intervals.

{ (0,2), (3, 7), (4,6), (7,8), (1,5) }

The maximum number of intervals overlapped is 3 during (4,5).

This can be asked in many forms in a programming competition. This CodeChef problem is one such an example. Go and test your knowledge if you have some idea about how to solve this.

Let us look at the solution approaches.

We first consider all the start and end point as a single entity and sort them in ascending order according the following criteria.
  • If the times are different, just sort according to time.
  • If the times are equal, we first place the end of interval.
Then we take a counter and a maximum counter. 

Iterate through all the points
  • If the point is start of interval we increment the counter.
    • Keep track of maximum counter
  • Otherwise we decrement the counter
At the end of this, we have the required result in maximum counter.

Another alternative solution could be to use the merge procedure used in merge sort. The steps are similar to the merge procedure.
  • Sort all the starting points and ending points in ascending order
  • Try to merge them into a single list
  • Use two variables overlap, and max_overlap to keep track of the current overlap and maximum overlap we have seen so far.
  • As long as we take element from starting point of the interval, increment overlap and update max_overlap.
  • If we are taking en element from ending point of the interval, decrement overlap.
At the end of this procedure, we have the answer in max_overlap.

Below is the simple C++ implementation of the above algorithms.

Tuesday, August 5, 2014

Last digit of a power

Given a number expressed in base, exponent form (ab) where a is arbitrary big number For example contains 100 digits, We have to write a program to find the last digit in it's expanded form.

Eg: 45712 has a last digit of 1

Since the range of numbers is huge, it is impossible to expand the number using standard data types like int, and long. We can use library classes to calculate the exponent (Eg. BigInteger in Java), but this is will take a long time to compute the result.

For this problem, we don't need to expand the result at all!

The trick here is to find the power of last digit in the base. The last digit in the expanded form always depends on the last digit of the base. It is always in the range of [0-9]

What if the exponent is also a big number?

We have to observe that the powers of single digit repeat after if we go on increasing the exponent.
Look at the following table. It gives a fair idea of our approach.

1 2 3 4
1 1 1 1 1
2 2 4 8 6
3 3 9 7 1
4 4 6 4 6
5 5 5 5 5
6 6 6 6 6
7 7 9 3 1
8 8 4 2 6
9 9 1 9 1

The the last digit in the power of 2 repeats every multiple of 4. Similarly the last digit in powers of 4 repeats every multiple of 2. and so on. 
Based on this observation we can write the following program to calculate the last digit in ab for arbitrary large numbers.