Category Archives: Competitive programming

Maximum number of contiguous ones with K zeros

Given an array of size N, containing only 0’s and 1’s, and a number K, what is the maximum length of the sub-array with contiguous 1’s with at most K 0’s?

For example consider the array

A = [1, 1, 0, 1, 0, 0, 1], K = 2, the maximum length is 5. i.e the sub-array A[0:4]

This problem can be solved using sliding window algorithm. Take two indexes front and back which defines a window. We keep expanding the window by incrementing the back index as long as the window contains less than or equal to K zeros. That means, at any time, the window contains at most K 0’s. If it exceeds K, we increment the front index to reduce the number of zeros to K. Continue this procedure until the back index reaches the end of the array. We also keep track of the largest window during this process.

This algorithm takes O(n) time.

Here is the C++ code.

Problem Source: SPOJ REPROAD

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

Partial sum queries

Given an array of numbers, we need to answer many queries of the form Sum(A[i]...A[j]),

For example, let the array be [15, 6, 1, 12, 7, 4, 10]

Sum(A[1:3]) = 15+6+1 = 22
Sum(A[4:6]) = 12+7+4 = 23
...

The simplest solution is to iterate through the elements from i to j and return the sum.
However this will be good enough if we have a small number of queries. What if we need to run many queries?
In worst case this is takes O(n2) time.

How can we reduce the time complexity?
If we pre-process the array by calculating the prefix array, we can answer each query in O(1) time.

For the above example calculate the prefix array by using the formula Prefix[i] = Prefix[i-1]+A[i]

Prefix = [15, 21, 22, 34, 41, 45, 55]

Now the partial sums can be calculated as follows

Sum(A[i:j]) = Prefix[j] - Prefix[i-1] if i > 1
= Prefix[j] if i=1

Here is the Java function which implements the above

long partialSum(int []prefixArr, int start, int end) {
long sum = arr[end];
if( start > 0)
sum -= arr[start-1];
return sum;
}

Facebook Hackercup 2016- Boomerang constellations problem solution

This problem is from the recently concluded Facebook Hackercup 2016 Qualification round. You can take a look at the problem statement in this link.

I am giving the abridged problem statement here. Given a set of coordinates in a 2D-plane, We have to find out the total number of pairs of lines with equal length and also share one end point.

For example, let us take the points {(0,0), (0,1), (1,0)}, there is one pair of lines, with a distance of 1. The line between (0,0),  (0,1) and the line between (0,0), (1,0).

The simplest way to solve this problem is this. Take a point (x,y) and try to calculate the distance to every other point. Maintain a map of distance to the number of other end points with that distance. This is O(n2 log n) solution.

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.

Odd number out

Given an array of numbers which contains all even numbers except one, or all add numbers except one.
How do you find the different number?

For example consider the array [1, 2, 3, 5, 9], 2 is the different number.
Similarly in the array [10, 6, 7, 24, 36], 7 is the different number.

This problem was originally appeared on Codeforces.

This is a simple implementation problem, which can be solved in one iteration.
When we are reading numbers, just keep track of the following information.

  • first even index
  • first odd index
  • even number count

At the end, check if the even number count is 1, If it is, then print first even index, otherwise print first odd index.
Here is the C++ code for this.

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.

Finding the the number at a given position in even odd array

Given a number N, an array is created by first adding all the odd numbers, and then adding all the even numbers below N, How do we find the number at a given position K?

For example consider N = 10, the array is [1, 3, 5, 7, 9, 2, 4, 6, 8, 10], the number at position K = 3 is 5, similarly at K = 6, the number is 2 etc.

Let us look at a solution for this. First of all, we need not build the entire array for finding out a number at a given position. We can simply find a formula to calculate the number, as the array can be divided into two halves, and both of them are in arithmetic progression.

If the given index is in first half, 2*(pos-1)+1, otherwise 2*(pos-n/2) will give the required answer. Following is the C++ implementation.

This problem was originally appeared in Codeforces.