Monthly Archives: February 2015

Finding the maximum element in a bitonic array

Given an array in which the elements are increasing up to a point and then decreases (this is also called a bitonic array), how do we efficiently find the maximum element?

For example, the input arrays can look like {1, 3, 5, 4, 2} ,  {11, 17, 25, 36, 24, 6}.

Basically we need to find the point at which the elements start decreasing. It can be anywhere in the array.

The obvious linear search for maximum takes O(n) time. But we can utilize the sorted property of two parts of the arrays to solve it in O(log n).

Here is how the algorithm works.

  • Go to the middle element and check if it is greater than both the left and right elements. If it is, then we found the maximum element. 
    • Eg: {1, 3, 5, 4, 2}
  • If the left element is greater than the middle element, we can ignore the right half and search only in left half. 
    • Eg: {1, 5, 4, 3, 2}
  • If the right element is greater than the middle element, we can ignore the left half and search only in right half.
    • Eg: {1, 5, 7, 9, 3}

We need to handle the cases where the middle element falls on the boundaries of the array. This happens when the entire array is sorted either in ascending order or descending order. Eg: {1, 2, 3, 4, 5} or {5, 4, 3, 2, 1}

  • If the right part is empty, and the middle element is greater than left element, we can eliminate the left part.
  • Similarly if the left part is empty, and the middle element is greater than right element, we can eliminate the right part.

Test cases:

  1. {1, 3, 5, 4, 2}
  2. {1, 2, 3, 4, 5}
  3. {5, 4, 3, 2, 1}
  4. {1}
  5. {1, 2, 2, 4, 5, 3}
  6. {10, 20}

 Here is the iterative C++ implementation of the above algorithm.

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.

Minimum number of symbols to change to make a chain

Given a string containing the only symbols ‘+’ or ‘-‘, how do we find the minimum number of changes to transform it to a chain. A chain of length N is the sequence of alternative + and – symbols.

For example “+-+-+” is a chain of length 5.
Similarly “-+-+-+” is a chain of length 6.
This is a problem from recently concluded Codechef contest. Here is the link to the original problem.

Some examples of input and output are as follows

Input   Output
————–
–+      1
-+-      0
+-+–+   2

We can solve this problem as follows. 
Observation:
Given the length of the sequence N, there are only two possible chains; One starting with – (-+-+….), and the other starting with + (+-+….).
So it is just enough to compare the input string to these two patterns and find the number of changes to make it a chain. Minimum of these two numbers gives us the answer.

For an example consider the input
+–++
Difference with +-+-+ is 2
Difference with -+-+- is 3
So the minimum number of changes to make it a chain is 2.

Here is the C++ code which implements the above.

Maximum length of subarray with non-zero elements

Given an array of of size N, How do we find the longest sub-array with all non-zero elements?

For example consider the array {34, 0, 18, 3, 0, 1, 4, 5, 0, 12}, the longest sub-array with non-zero elements is 3 i.e {1,4,5}.

This problem is from Codechef. Follow this link to solve this problem in your own.

The solution is simple. The array contains non zero segments of numbers separated by one or more zeros. While traversing the elements, use two variables current_len, and max_len to track the length of the current segment and maximum segment length seen so far.

Here is the Python implementation of the above. This runs in O(n) time.

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.

Finding a sub list with least max-min difference – Codeforces puzzle

This is a problem from Codeforces. Please follow this link to solve this problem on your own.

The abridged problem statement is as follows.

You are given an list of numbers, and sub-list size as input. The challenge is to find a sub-list such that the difference between the maximum and minimum numbers in that sub-list is minimized.

For example consider the numbers {36, 6, 12, 42, 24, 50}, and we have to find a sub-list of size 4. By choosing {36, 42, 24, 50}, we can have a least difference of 26 i.e 50-24.

The solution is to first sort the numbers in ascending order, and move a sliding window of sub-list size from begin to end while keeping track of the minimum difference between first and last numbers of the sub-list.

Tracing with the above example, after sorting the list becomes {6, 12, 24, 36, 42, 50}
We start with 6, 36, the difference is 30
move on to 12, 42, the difference is 30
move on to 24, 50, the difference is 26
So the minimum difference is 26.

This algorithm runs in O(n*log n) time because we have to sort the list. the actual algorithm takes O(n), linear time.

Here is the C++ code for the same.