Category Archives: Competitive programming

Maximum increasing sub array

Given an array of numbers, how to find the maximum length of increasing (non-decreasing) continuous sub-sequence?

For example consider the array [7, 9, 1, 3, 5, 8, 2], the maximum length is 4. Similarly for [23, 10, 18, 18, 6], it is 3.

This is a straight forward implementation problem (appeared on Codeforces). Following is an implementation of O(n) algorithm.

Check if an array has a sub-array with given sum

Given an array of numbers and a sum, how to check if there is any sub-array with the given sum.

For example consider an array A = [7, 2, 9, 1, 5], and the sum is 12, then we can find a sub-array [2, 9, 1] which sums up to 12. So the answer is Yes. If we want to check for sum 14, we can not find a sub-array with that sum.

A simple method is to check if a sum can be found for all possible sub-arrays. This solution takes O(n3) time.

A more efficient method is the sliding window method. We maintain two indices, one indicates the beginning of the window, and the other indicates the ending of the window.

While iterating through the elements, we increment the end-index as long as the current sum is less than or equal to the target. If we find the target sum, then we are done. If we exceed the target sum, we deduct the beginning elements from the current sum until it is less than or equal to target sum.

This approach takes O(n) time. Here is the C++ code.

Decreasing string

Given a number K, Find the shortest and smallest string  which has K positions in it, such that the character at that position is alphabetically greater than the character immediately after it. Only the lower case alphabets [a-z] are allowed.

For example consider K = 1

“ba” is the shortest and smallest string possible. There are other possibilities like “ca”, “bad”. But “ca” cannot be the answer because “ba” is alphabetically smaller than “ca”. Similarly “bad” cannot be the answer because it’s length is greater than “ba”.

This problem is from Codechef. If you want to solve it, follow the problem link.

Here is how we can solve the problem. Let us look at some of the answers.

K = 1, “ba”

K = 2, “cba”

K = 3, “dcba”…

If you observe the pattern, this is simply reverse order of alphabets. We can happily reverse the alphabets if K < 26. What happens if K = 26? The pattern repeats, and the repeating pattern should be added in the beginning.

So for K = 26, the answer is “bazyxwvutsrqponmlkjihgfedcba”.

Here is the Python implementation of this algorithm.

Up down array

Given an array of numbers A[N], how do we arrange them in the following order.
A[0] <= A[1] >= A[2] <= A[3]...A[N-1]

For example consider the array A =[6, 9, 36, 24, 42]

The answer can be [6, 36, 9, 42, 24]. There can be multiple answers also like [6, 42, 9, 36, 24]. We have to find out one such answer.

We can solve this problem in a simpler way by sorting the array first. Considering the same example as above

Sorted(A) = [6, 9, 24, 36, 42]

Method1: Start from the second element and swap the elements in pairs

6, 9<-> 24, 36<-> 42 ===>  6, 24, 9, 42, 36

Method2: Interleave the elements of the second half into the first half in reverse order

It becomes 6, 42, 9, 36, 24

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.

XOR of all sub arrays

Given an array of elements, how do we find the XOR of each sub-array and XOR of those results?

For example let us consider the array [1, 2, 3], all possible sub-arrays are

XOR[1] = 1
XOR[1, 2] = 1 ^ 2 = 3
XOR[1, 2, 3] = 1 ^ 2 ^ 3 = 0
XOR[2] = 2
XOR[2, 3] = 2 ^ 3 = 1
XOR[3] = 3

And the result XOR[1, 3, 0, 2, 1, 3] = 2.

Brute force solution:
From the above example, you can see that an array of 3 elements has 6 sub-arrays. Similarly you can verify the count by listing the sub-arrays for N= 4 and N= 5. In general, for an array of N elements there will be N*(N+1)/2 sub-arrays. We have to calculate the XOR of each of these sub arrays. So an outline of algorithm can be as follows.

for i in range(1,N)
   for j in range(i,N)
      for k in range(i,j)
         x = XOR(x,A[k])

This is clearly not en efficient solution and take O(n3) time. We can also use dynamic programming to pre-calculate the XOR values so that time can be reduced to O(n2). But is there any better method?

Efficient Solution:
Observe how many times, each element appear in all the sub arrays. In the above example
1 – 3 times
2 – 4 times
3 – 3 times

Consider 0-index, in general A[i] appears (N-i)*(i+1) times. 

We also know that if an element is XOR’ed with itself even number of times, it is zeroed out. and if it is odd number of times, it remains the same. For example

V ^ V ^ V ^ V = 0
V ^ V ^ V = V

Consider the two cases when the number of elements N is Even or Odd
N is even, each element appear even number of times:

N= 2, 
A[0] – 2 times
A[1] – 2 times
N = 4,
A[0] – 4 times
A[1] – 6 times
A[2] – 6 times
A[3] – 4 times

This is because either (N-i) or (i+1) is always even for all values of i.
Hence, for an array of even length, the XOR of all sub-array becomes Zero.

N is odd, the elements at even index will only prevail in the final result.

The following C++ program implements the above approach. The time complexity of this algorithm is O(n).

Character to be removed to become a palindrome

Given a string, We have to find out by removing which character, it becomes a palindrome.

For example consider the string “racercar”, the character ‘r’ at index 4 should be removed to become a palindrome.

The approach here is simple.

Start from both ends of the string and compare both characters. If they are equal, we increment the front index and decrement the back index. If they are not equal, one of the characters needs to be removed. We can check this by verifying if a palindrome can be formed by removing the front character or the back character. Repeat the above procedure until both indices meet each other.

We are printing the index of the character to be removed. If the string is already a palindrome, we print -1.

This solution has O(n) time complexity.

Here are the implementations in C++.

How does a radix sort work?

Radix sort is an integer sorting algorithm. As it’s name indicates, it sorts a list of numbers based on the digits of the numbers. 

It’s a linear time sorting algorithm which is different from the comparison based sorting algorithms like quick sort or heap sort. Counting sort is also a linear time sorting algorithm which is explained in my previous post.

Let us understand this algorithm using an example. 
Consider the array [235, 10, 784, 69, 51]

We first sort the numbers based on the least significant digit, i.e the digit at 1’s place. It becomes [10, 51, 784, 235, 69]. Observe that the these numbers are now sorted according to it’s last digit ([0,1,4,5,9]).

Next we consider the digits at 10’s place and sort them. It transforms to
[10, 235, 51, 69, 784]. These are sorted according to the last but one digits ([1,3,5,6,8])

Similarly in the next step it becomes [10, 51, 69, 235, 784]

Now the entire array is sorted! We no longer need to sort array because we have at most 3 digits in any number.

Implementation details:
Suppose there are at most D digits in any number, we call the counting sort D times for each place.

Let us briefly know how counting sort works. For more details, you can check my previous post.

It first groups the numbers into buckets. The result of this is a count array of size 10 (assuming the numbers are in the range 0-9). 

Calculate the prefix array of this, we get the sorted positions of given numbers.

Then we use a temporary array to arrange the numbers in sorted order.

An alternative implementation could be to maintain a list of numbers for each bucket, and merging them to a sorted array. But this approach takes extra memory for the list of buckets.

The following code shows  the implementation of the above algorithm.
Exercise: Try to solve this SPOJ problem using radix sort.