Category Archives: CodeChef

Maximum elements of array

Given an array A of size N, We want to perform several iterations as described below.

Select any index i such that 1 <= i <= N, Mark A[i] = 0, move left by filling each element one greater than it’s right
Similarly move right, and fill each element which is one greater than it’s left.

For example consider an array of length 5, and we choose the index 3, the array would be

A = [2, 1, 0, 1, 2]

If we perform several iterations by choosing different indexes each time,
we have to output the maximum number, each element can get during all the iterations.

Consider that we repeat the procedure for the above array with Index 2
A = [1, 0, 1, 2, 3]

So after two iterations at indexes 2, and 3, maximum elements would be
MAX_A = [2, 1, 1, 2, 3]

To find MAX_A, at first, it looks like we need to repeat the procedure m times for m indexes,
which leads to O(m*n) complexity solution.

What will be the maximum number an element can get? N-1
How? Lets consider the same array as above, choose index 1, the array would be
A = [0, 1, 2, 3, 4]
Choose index 5, the array would be
A = [4, 3, 2, 1, 0]

So it is enough to perform the iteration with the left most and right most indexes,
the maximum element at each index i would be max( abs(i-left), abs(i-right))

So the time complexity will be O(n).

Here is the C++ code for the same.

Problem Source: The Army – Codechef

Path length between two binary tree nodes

Given a full binary tree (all nodes except leaf nodes have left and right child) represented as shown below.
If the root is labelled i, it’s left child is labelled 2*i and right child is labelled as 2*i+1.
1
/   \
2     3
/  \   / \
4  5  6   7

Given two nodes from this tree, how do we find the length of the path between them?
For example the path length between 2 and 3 is 2 (2->1->3)
Similarly path length between 4 and 1 is 2, and between 4 and 7 it is 4 (4->2->1->3->7)

In a binary tree, two nodes can be connected in two possible ways.

  • Either one of the nodes can be ancestor of the other, or
  • Both of them are connected by some common ancestor.

For example, take 1 and 5, 1 is an ancestor of 5.
Take 4 and 5, they are connected by their lowest common ancestor 2, so the path goes has to via 2.
So this problem can be solved by finding the Lowest Common Ancestor (LCA) of the two nodes and adding the distances between the nodes to their LCA.

We use the bottom up approach here. Start from the given two nodes and try to search for lowest common ancestor by going up since we can easily go the parent node by dividing the node by 2. While finding the LCA, we can also calculate the path length.

Since we traverse through the tree for at most the height of the tree, the time complexity will be O(log n).

Here is the C++ code.

Problem source: Codechef

Billing algorithm

This problem is from Codechef. I am re-wording it for more clarity.

A garments shop has “Buy 2, Get 2” offer for it’s customers. Whatever the items may be, they charge for costliest items from an order and give the cheapest ones free.
However we can divide the items into multiple orders to save more.

For example, Let us say we have 6 items with prices 200, 600, 100, 900, 800, 700. If we take them as one order, we will have to pay 3000.

6 items are divided into two groups {900,800,200,100}, {700,600} because they charge for highest price items. So the total bill would be 900+800+700+600 = 3000
Suppose we divide the items into two groups {900,800,700,600}, {200,100} we need to pay only 900+800+200+100 = 2000

Now the problem is, given a list of prices, how do we calculate the minimum amount we need to pay?

This is a simple greedy algorithm. We just need to sort all the prices in descending order and group them into 4 per order. The last order might contain less than 4 items.

Here is the C++ code for the same

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

Finding the number in a shuffled array

Given an array [1, 2, 3,…N], we apply a series of reversal operations on different range of indices [L,R].
How to find out the position of a number after these operations are applied?

For example consider an array of 5 numbers [1, 2, 3, 4, 5] and the number 2.

Reverse elements between 1, and 3, the array becomes [3, 2, 1, 4, 5]
Reverse elements between 3, and 5, the array becomes [3, 2, 5, 4, 1]
Reverse elements between 2, and 5, the array becomes [3, 1, 4, 5, 2]

So the final position of 2 is 5.

This problem was originally appeared in Codechef.

If we want to track just one number, we need not perform reversal operations everytime. This process takes O(n^2) time in worst case.

As we perform the reversal operations, we just need to track what is the new position of target number.

How do we track the position?
Consider the positions L = left, R= right, C = current and the distance between L and C is X,
After we reverse the elements between L, R, C will be placed x steps before R

C – L = R – X
X = R + L – C
The new position of C will be (R+L-C)
The position of C will not be altered if we are reversing the part which includes C.

Here is the C++ code for the same which runs in O(n) time.

Maximum Xor of two bit patterns

Given two numbers A, B, What is the maximum value of A' XOR B', where A', B' are obtained by permuting the binary representations of A, B respectively.

For example assume A = 3, B = 1 and they are represented in 4 bits. A = 0011, B = 0001 in binary. Suppose A' = 1100, B' = 0010, then we get the A' ^ B' = 1110 = 13. So 13 is the answer. For no other values of A’, B’, the XOR will be maximum.

Let us look at another example A = 3, B = 7, again represented using 4 bits. A' = 0011, B' = 1101 and A' ^ B' = 0011 ^ 1101 = 1110 = 14. So 14 is the answer.

This problem was originally appeared on Codechef. The problem has 3 inputs N (number of bits), A, B. How many 1s are possible in the result number?

Since 1^0 = 1 and 0^1 = 1, to get a 1 in the final result, We should have a

  • 1 bit in A, and 0 bit in B or
  • 0 bit in A, and 1 bit in B

So the total number 1s possible in the result is Minimum( 1s in A, 0s in B) + Minimum( 0s in A, 1s in B). The remaining bits are Zeros.

How should we arrange these bits to get the maximum value? All 1s should be pushed to left (Most significant bits). So the result will be of the form 1111…00

Here is the Java code which implements the above approach.

How to check if sequence is a sub sequence of another

Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.

For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]
where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]

The algorithm here is simple. 
  • Let us assume two indices i, j point to the beginning of sub-sequence and sequence respectively.
  • Do the following until we reach the end of any sequence.
  • If both the elements are same, increment both indices.
  • Otherwise increment j only.

At the end of this iteration, if we have seen all the elements of sub-sequence in the given sequence, we are done! otherwise we have not found!

Here is the code in C++ which implements the above approach. This runs in O(n) time and O(1) space. For Python code click here. For Java code click here.

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.

Ambiguous permutations

Given a permutation of numbers from 1 to N, We can represent it in two ways.

For example, let us consider a permutation from 1 to 5
P = [2 4 1 5 3]
This representation directly indicates the position of each number. i.e 2 is first, 4 is second and so on.

Alternatively, this can also be represented in inverse permutation form.
A = [3 1 5 2 4]
Assuming 1-based index, each number at the index ‘i’ indicates that the number ‘i’ is positioned at A[i] in the actual permutation. So this means that 1 appears at index 3, 2 appears at index 1, and so on.

There are some cases when the actual permutation and the inverse permutation are same. We call it as an ambiguous permutation. Now the problem is how do we check if the give permutation is an ambiguous permutation?

The solution is simple. We have to create an inverse permutation in another array, and check if it is same as the original permutation. Calculating the inverse permutation is discussed in my previous post.

Following is the C++ code. It runs in O(n) time and O(n) space.

Minimum number of chages to make equal groups

Given an array of numbers, how do we find the minimum number of changes(additions/subtractions) to the elements so that each number in the array is same or equal.

For example given the array {1, 2, 3, 4}, the minimum number of changes are 3. i.e we can choose any of the four elements and make the other three elements equal to the chosen element.

Similarly given the array {56, 29, 112, 29}, the minimum number of changes to make is 2. We can choose 29 as the common element and change the other two elements.

This problem is from recently concluded Codechef contest. Click on this link to read the complete problem statement.

The solution is evident from the second example. This is the problem of finding the number of occurrences of a most frequently appearing number (mode) and subtracting it from the total number of elements.

There are at least two different approaches to implement the solution. 
One is to sort the array (takes O(n log n) time) first and find the maximum frequency in O(n) time.
The other is a map based approach to store the frequencies of elements while iterating through all the elements and find the maximum among them. This will take O(n) time bust consumes O(n) extra space.

Below is the C++ implementation of the first strategy. Read my previous post for the implementation of map based method.