Category Archives: Mathematics

Counting pairs in array

Given an array A of distinct numbers, how to count the number of pairs (i,j) such that
A[i] < A[j]

For example, let us consider A = [2, 1, 3]
the pairs are (1,2), (1,3), (2,3). So there are 3 pairs.
Similarly for A = [10, 6, 9, 2], there are 6 pairs

This problem was originally appeared in Codechef.

One straight forward solution is to loop through all possible pairs and count them.
But this has O(n2) time complexity.
We actually don’t need to count all the pairs because the elements are distinct.
Suppose we arrange the elements in sorted order

A = [1, 2, 3]
then the pairs are (1, 2), (1,3), (2,3)
A = [2, 6, 9, 10]
the pairs are (2, 6), (2,9), (2,10), (6, 9), (6, 10), (9,10)

If there are n elements in an array, there will be n*(n-1) pairs. Since the all the elements are unique, half of them satisfies the given property.

So the answer will be n*(n-1)/2

Minimum number of squares formed from a rectangle

Given a rectangle of some length and width, How do you divide them into minimum number of squares? This is a problem from Codechef.

For example give a rectangle of size 2 x 4, we can make them into two squares of 2 x 2.
Similarly a rectangle of size 3 x 7, can only be divided into 21 squares each of size 1 x 1.

So what is the logic behind this?
The length and width should be divided in same equal parts, and that part should as greater as possible. So we have to find the GCD(Greatest Common Divisor) of the length and width of the rectangle. Then the minimum number of squares can be calculated by
l/g * w/g. where l = length, w = width, g = GCD(l,w)

Here is the C++ code which implements this.

GCD queries

This problem is from Codechef January challenge. Click on the link to try this problem on your own.

The problem statement is as follows.

Given an array of size N and two indices L and R. We need to find the GCD (Greatest Common Divisor) of all the array elements except in the range [L,R]. The indices start from 1. We have to answer multiple queries of this type.

An obvious solution could be to find the GCD of all the elements from [1,L-1] and [R+1,N] and find the GCD between these two numbers. But this solution is O(n) for each query in the worst case.

First let us pre-process these array to gain some efficiency. Define cumulative GCD as follows.

If A is an array of N elements, the cumulative GCD of an array A from left to right consists of the following.

cgcd[0] = A[0]
cgcd[1] = gcd(cgcd[0], A[1])
cgcd[2] = gcd(cgcd[1], A[2])
…. and so on

Lets create an array fgcd which stores the cumulative GCD from left to right. Also create an array bgcd which stores the cumulative GCD from right to left.

After calculating these values, answering the query is simply finding the GCD of fgcd(L-1) and bgcd(R+1).

Here is the C++ implementation of the above. This each query takes only O(1) time and it takes O(n) extra space to store the pre-processed values.

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.

Printing all K combinations from N numbers

Given two numbers N and K, how do we print all the K-combinations of numbers from the set {1,2,…N}.

For example consider N = 4, K = 3, the possible combinations are
[
 [1, 2, 3]
 [1, 2, 4]
 [2, 3, 4]
 [1, 3, 4]
]

Let us look how to solve this combination problem. This problem can be recursively defined as follows. To generate K-combinations from N elements, we have two possibilities.
  1. Generate K-Combinations from (N-1) elements.
  2. Generate (K-1)-Combinations from (N-1) elements and append N to all of them.
Let us simulate this with an example. Assume N = 3, K = 2

Generate 2-Combinations from 2 elements i.e N = 2, K = 2
This will be just one combination i.e [1, 2]

Generate 1-Combinations from 2 elements i.e N = 2, K = 1
[1], [2]
Append 3 to each of them
[1, 3], [2,3]

So there are totally 3 combinations [ [1, 2], [1, 3], [2, 3] ].

Here is the recursive implementation in C++.

Implementing power function

Given the base and exponent, how do we implement the pow(base,exp) function efficiently?

For example 
pow(2.0,5) = 32
pow(0.4,2) = 0.16
pow(2.0,-2) = 0.25

For simplicity, let us assume that the base can be a decimal number and exponent can be any integer. A straight forward implementation that comes to mind is simply multiplying the base with itself for ‘e’ times where e is the exponent.

There is one more efficient way to calculate this value using divide and conquer technique. If we have to calculate an, we can divide the computation into two similar tasks i.e we can calculate an/2 once, and multiplying it with itself gives the required value
an = an/2*an/2

Here is the C++ implementation of the above algorithm. This reduces the number of multiplications required for calculating the power. Observe how different test cases are handled in the program.

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


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.

How to check if a given number is Fibonacci number

How to check if the given number is a Fibonacci number?

A Fibonacci series starts with 0, 1. Remaining elements are formed by adding previous two numbers.

Here are a few Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

If a number is given, a straight forward way to check if it is a Fibonacci number is to generate the numbers one by one until we get the required number or greater than that.
Here is the python code do that.
One more approach is based on a property of Fibonacci numbers
If 5*x2+4 or 5*x2-4 (or both) is a perfect square, we can conclude that it is a Fibonacci number. 

The C++ code is given below.



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