Monday, December 22, 2014

Number of ways of arranging 0, 1

Given 'N' zeros and 'M' ones, In how many ways can we arrange them to form a string of length (N+M)?

For example if we have 2 zeros and 2 ones, we can arrange them in 6 ways
0011, 1100, 0101, 1010, 1001, 0110

If there are N symbols to arrange, The number of ways to arrange them in a sequence is called a permutation problem. This number is simply N! (N factorial).

We have (N+M) symbols in total and N symbols are one type and M symbols are another type, So the number of permutations become (N+M)!/ N!*M!

Another way to look at the problem is using combinations. We have (N+M) places either
  • We have to choose N spaces to fill zeros, in the remaining places, we fill one
  • Or We have to choose M spaces to fill ones, in the remaining places, we fill zero
The number of ways to choose R objects from N objects is called a combination problem. This is represented by C(N,R) = N!/(N-R)!*R!

So for our problem there are (N+M) symbols and we need to either choose N zeros or M ones. So it becomes C(N+M,N) or C(N+M,M)

Both reduce to (N+M)!/N!*M!.

If we try to implement the above formula as it is in code, we have a problem of data overflow.

For example consider 21! = 51090942171709440000, we cannot represent in a long integer also. If we are calculating C(21,10), simply calculating factorials with built in data types result in data overflow even though the result can be represented in those types. C(21,10) = 352716.

In competitive programming, it is sometimes asked to reduce this value using a modulo operation. For example calculate C(n,r) modulo 10007 for arbitrarily large numbers say 1 <= n,r <= 1000. In these cases also, using the factorial formula does not serve the purpose.

We have another formula to calculate C(N,R) using recursive definition.
C(N, R) = C(N-1, R-1) + C(N-1, R)
You can easily understand this by using Pascal triangle.
If we implement the algorithm using this formula, we can find the result for a much better range of numbers .

Here is the Java implementation. For this problem I assumed the range of 1000 for N and M. Also it calculates the result modulo 109+7

Thursday, December 18, 2014

Number of ways to represent an integer as sum of two squares

Given a number, we have to find out the number ways to express it in the form of sum of two integer squares.

For example let us consider 25, it can be written as sum of the pairs (0,25) (9,16)

24 cannot be written as a sum of any two squares.

Mathematically this problem is to find the roots of the equation x2+y2-n = 0 where n is given.

The algorithm for this problem is simple. let us start i with 0 and check if (n-i*i) is a perfect square. We repeat this process until (n-i*i) is greater than i*i

Take the example of 25, Here is the trace of the algorithm

i          n-i*i      Result
0          25        - Yes
1          24        - No
2          21        - No
3          16        - Yes
4          9         - break

Here is the C++ code to do this.

Thursday, December 11, 2014

Counting triplets with given sum

Given an array of distinct numbers, how do we count the number of triplets with given sum?

For example let us consider the array {5, 2, 7, 8, 4, 3} and the sum is 14, 
There are 3 triplets with the given sum

A brute-force algorithm will take O(n3) time. But this problem can also be solved based on 2 Sum problem. Here is the approach.
  • Sort the array first.
  • Fix the first element in the triplet, and search for a pair of elements whose sum is (Sum - Fixed element)
  • Repeat the above step for all the elements
We are essentially searching for a pair of elements for each fixed element. So the time complexity of this solution would be O(n2).
One variation/follow-up of this problem could be to find out the number of triplets with sum less than or equal to the given value.
Considering the first example again, there are 8 triplets with sum less than or equal to 14.
2 3 4
2 3 5
2 3 7
2 3 8
2 4 5
2 4 7
3 4 5
3 4 7
The solution for this is similar to the first problem and uses the trick discussed in my previous post

The code for both is given in the following Java program.

Tuesday, December 9, 2014

Number of pairs with sum less than or equal to given value

Given an array of numbers, Count the number of pairs with sum less than or equal to K

For example consider the array {5, 1, 12, 3, 6}
pairs with sum <= 10 are {(1,3), (1,5), (1,6), (3,5), (3,6)}
So there are 5 pairs with the given constraint.

In one of the previous posts, we have seen how to find a pair with given sum in the given array. This problem is a variation of that.

Let us look at the algorithm.
  1. First sort the array in ascending order.
  2. Take two indices one(b) pointing to the start of the array, and the other(e) pointing to the last element of the array.
  3. If A[b]+A[e] <= K
    1. A[b] + A[i] <= K for b < i < e. Hence (e-b) elements satisfy the given property.
    2. Increment b and decrement e and repeat step 3
  4. Otherwise decrement e
  5. Repeat step 3 until b and e meet each other.

A[0] A[1] A[2]... A[N]
b-->            <--e

Considering the above example 
{1, 3, 5, 6, 12} let b = 0, e = 3 and K = 10

1  3  5  6  12
b        e


If we add 6 or 5 or 3 to 1, the sum is less than 10. At this point, we can increment the pair count in one shot.

Here is Java implementation of the above algorithm. This solution runs in O(n log n).

Friday, December 5, 2014

Maximum sum path in two sorted arrays

Given two sorted arrays of size M and N, Find a sequence of elements from both the arrays whose sum is maximum. The sequence can begin with any of the two arrays and can jump from one array to another array if there is a common element.

Let us consider the following example
Array1 = {1, 5, 9, 15}
Array2 = {7, 9, 12}

The maximum sum is 7 + 9 + 15 = 31

Similarly let us examine a little more complex example

Array1 = {1, 3, 7, 10, 15, 19}
Array2 = {2, 4, 6, 7,  9, 15, 20}

The maximum sum is 2 + 4 + 6 + 7 + 10 + 15 + 20 = 64

This problem is similar to finding the common elements between two sorted arrays and also similar to the merge procedure in merge sort. You can check out my previous post on this.

Start with two indices pointing to the beginning of two arrays. 

We maintain two variables sum1, sum2 to keep track of the partial sum. Compare the two elements, move the index with lesser element forward and add it to it's corresponding sum. 
We do this until we find an equal element; at this point we add the maximum of two sums to a global maxSum variable and repeat the same procedure.

Let us trace the algorithm for the first example

  • sum1 = 0, sum2 = 0, ind1 = 0, ind2 = 0, maxSum = 0
  • sum1 = 1, sum2 = 0, ind1 = 1, ind2 = 0, maxSum = 0
  • sum1 = 6, sum2 = 0, ind1 = 2, ind2 = 0, maxSum = 0
  • sum1 = 6, sum2 = 7, ind1 = 2, ind2 = 1, maxSum = 0
  • sum1 = 0, sum2 = 0, ind1 = 3, ind2 = 2, maxSum = 7
  • sum1 = 15, sum2 = 12, ind1 = 3, ind2 = 2, maxSum = 16
  • We reached the end; update maxSum = 16+15 = 31
Here is the C++ code for the same. It runs in O(m+n) time where m, n are the lengths of the two arrays respectively.


Wednesday, December 3, 2014

Finding the longest consecutive subset

Given an array of positive and negative numbers(distinct), How do we find the length of the longest consecutive subset?

For example consider the below array
{3, 6, 1, 2, 5, 7, 8}
It contains {5,6,7,8} as the longest consecutive subset. So the answer is 4.
Similarly for {2, 4, 6, 8}, the answer is 1 as there are no consecutive numbers.

Lets discuss two algorithms to solve this problem.

Method based on sorting: 
We sort all the elements in ascending order. This would take O(n log n) time. Then we compare the adjacent elements to check if they are consecutive. If any two elements are not consecutive, we break the sequence and update the maximum length. getMaxConsecutiveSubset1() method in the code implements this algorithm. The overall complexity of this algorithm is
O(n log n).
Method based on Hash map:
Let us take a Hash map which stores the all the elements with a flag for each which indicates if it is visited or not visited.
  • Initially we store all the elements to the map with visited flag as false. 
  • For each element do the following 
    • If it is not visited earlier 
      • Mark the element as visited 
      • Initiate a sequence of length 1 
      • Try to extend this sequence backward by marking the elements visited 
      • Try to extend this sequence forward by marking the elements visited 
      • Update the maximum sequence length

Here is the Java code which implements the above algorithm. It runs in O(n) time and O(n) space.

Monday, December 1, 2014

Finding increasing triplet in an array

Given an array of distinct numbers, we have to find if there is any triplet of type (A[i], A[j], A[k]) such that A[i] < A[j] < A[k] and i < j < k.

For example consider the array {6, 1, 5, 2, 4}

We have a triplet {1, 2, 4} which satisfies the given criteria.

Where as the array {4, 1, 5, 3, 2} does not have any such triplets.

Simple algorithm:

For each element we can try to find the lesser element to the left of it and find the greater element to the right of it. This will obviously give the required result. But this algorithms in O(n2).

printIncreasingTriplet1() method implements this approach.

Linear time algorithm:
We declare two arrays leftMin and rightMax. leftMin stores the minimum element seen so far up to the given index. Similarly rightMax stores the maximum element seen so far up to the given index but from reverse order.

We are essentially calculating the lesser elements to the left and greater elements to it's right for each element.  In the next step we need not search for the lesser and greater elements for all elements. They are simply available in leftMin and rightMax at the same index.

printIncreasigTriplet2() in the code implements this approach. This runs in O(n) time and takes O(n) space.