Category Archives: Divide and Conquer

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.

Counting the number of inversions in a list

Given an array of numbers, how do we count the number of inversions in it?

An inversion is an ordered pair if indices (i,j) such that i < j and A[i] > A[j] .

For example consider the array {3, 2, 1, 5, 4}
The inversions are {(0,1), (0,2), (1,2), (3,4)} totaling 4.

We can always use the brute force approach of comparing all possible pairs of numbers to check if each pair is an inversion or not. This takes O(n2) time.

How do we solve this efficiently?

We can modify the merge sort procedure to count the number of inversions also!

Please check out my earlier post on Merge sort to understand how it works.

Here are the steps.
  • First count the inversions in the left part
  • Count the inversions in the right part
  • Count the inversions if they are merged using modified merge procedure
  • Adding the three counts gives the actual result 
We need to change the merge procedure to count the inversions. The merge procedure works like the following.

We have two sorted arrays to merge into another array.

{1, 3, 5, 7} + {2, 4, 6, 8} = {1, 2, 3, 4, 5, 6, 7, 8}
  • Take two pointers to start of the two arrays.
  • Compare the two elements to see which element goes to the sorted list first.
  • Increment the corresponding index.
  • Repeat the above steps until we reach the end of either of them.
  • Add the remaining elements if any.
While comparing the two elements if the left element is lesser than right element, we simply proceed.
If the right element is lesser than left elements, then it is also lesser than all elements to the right of left element. So increment the inversion counter accordingly.
For example
{…. 5, 9, 12, 15, …}
{…..3,….}
3 Appears in the right and 5 appears in left. So we can count all the inversions (5,3), (9,3), (12,3)… in this step itself.
Here is the C++ code which implements the above algorithm. The time complexity of this implementation is O(n log n).


    Computing the power of a given number

    Given a base and it’s exponent, how do we efficiently evaluate it?
    In other way, how do implement a pow() function which is typically provided by a library.

    For example 210 = 1024.

    The simplest method that comes to our mind is multiply the base with 1 in a loop for exponent times.

    double result = 1;
    for( i = 0; i < exp; i++ )
    {
        result = result*base;
    }

    This method runs in O(n) time complexity where n is the exponent. 

    We can make this efficient by using Divide and Conquer technique. Considering the above example, 210 can be calculated as follows.
    210 = 25 * 25
    25 = 22 * 22
    22 = 21 * 21

    In each step we avoid computing half of the product which can save us time.
    Here is the C++ function to calculate the result. In this function I have handled negative exponents also. This method runs in O( log n) complexity.

      double pow(double x, int n) 
      {
            int absn = abs(n);

            if( absn == 0 )
            {
                return 1.0;
            }

            else if( absn == 1)
            {
                return (n < 0) ? (1/x) : x;
            }
           
            double temp = pow(x, absn/2);
            double result;
            
            if( absn % 2 == 0 )
            {
                result = temp*temp;
            }
            else
            {
               result = temp*temp*x;
            }
            return ( n < 0 )? (1/result) : result;
      }

    Finding an element in a circularly sorted array

    Given a circularly sorted array, how to search for an element efficiently?

    For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.


    Since the array is sorted but rotated, we can expect it to be solved using the binary search technique.

    We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.

    Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .

               if( arr[low] <= arr[mid]) //left half is sorted
            {
                //If target lies in first half

                if( s >= arr[low] && s < arr[mid] )
                    high = mid – 1;
                else
                    low = mid + 1; // narrow down to right half
            }
            else // Right half is sorted
            {
                if( s > arr[mid] && s <= arr[high] )
                    low = mid + 1;
                else
                    high = mid – 1;
            }

    Here is the iterative implementation of the above algorithm. This algorithm runs in O( log n ) time complexity.

     

    How many times a sorted array is rotated?

    Given a circularly sorted array of unique elements, how do we efficiently find the number of rotations?

    For example the array [4, 5, 1, 2, 3] is (right) rotated twice.

    Before proceeding to find a solution, let’s note some observations.

    To find the number of rotations, we have to find the smallest element in the array. If we find the index of the smallest element in the array, that will indicate the number of rotations.

    In the above example, the smallest number is 1 which is located at index ‘2’. We can easily verify that the array is rotated twice.

    A simple approach could be to use a linear search to find the least number and return it’s index. This approach will obviously take O(n) time. Can we perform better than that?

    Yes, it can be done by utilizing the sorted property of the array. Here is how we can do this.

    Just like Binary search, we can use divide and conquer approach. We write a recursive function which will take the array, lower and upper bound as its parameters.

    We first check whether the array is sorted from the beginning (not rotated). This can be done by checking if array[low] <= array[high]. If it is not rotated, we can simply return the index low.

    Next we check if the middle element is the smallest element by comparing it with the previous and next elements.

    if( array[mid] < array[prev] && array[mid] < array[next] )

    If this condition is satisfied, then we return mid. One caution while calculating the next and previous indices is to consider the array boundaries. We have to assume that the array is circular.

          //if mid is at 0, consider last element as previous
         int prev = (mid – 1 + len) % len;
       //if mid is the last element, consider next element as the first

         int next = (mid + 1) % len;

    Next, we check which portion is already sorted. If the left portion is properly sorted (without rotations), we search in the right half. Otherwise we search in the left half.

         if( arr[low] <= arr[mid] )
            return findRotations(arr, mid+1, high);
        else
            return findRotations(arr, low, mid-1);
    Here is the C++ code which implements the above algorithm.

    Even more simplified version of the algorithm is given below. 

    int findRotationCount(const vector<int>& arr)
    {
    int low = 0, high = arr.size() - 1;

    while( arr[low] > arr[high] )
    {
    int mid = low + (high - low)/2;
    if( arr[mid] > arr[high] )
    low = mid + 1;
    else
    high = mid;
    }
    return low;
    }
    int findRotateCount(const vector<int>& arr, int low, int high)
    {
    if( arr[low] > arr[high] )
    {
    int mid = low + (high-low)/2;
    if( arr[mid] > arr[high] )
    return findRotateCount( arr, mid+1, high);
    else
    return findRotateCount( arr, low, mid);
    }
    else
    return low;
    }

    How does Quicksort work?

    Quick sort is a comparison based sorting algorithm. Like Merge sort, this also follows divide and conquer algorithmic pattern.

    Quick sort works as follows. 

    A random element from the array is chosen as a pivot element. A pivot element is a special element which divides the array into left part and right part. All the elements to the left of pivot ( left part) must be less than or equal to pivot, and all the elements to the right of pivot( right part) must be greater than pivot.

    At this point it is easy to understand that the pivot element is in it’s position and only left, and right parts needs to be sorted. We use recursive call to sort these parts.

    Here partition process is the key to sorting. 

    Consider the following example to understand the partitioning process.

    Initial array: 4 is chosen as pivot for simplicity


    4
    7
    3
    6
    9
    2
    8
    5
    1


    After partitioning:


    2
    1
    3
    4
    9
    6
    8
    5
    7

     
    You can get a good understanding of the whole procedure if we look at the following animation (Image courtesy: Wikipedia).

    Here is the C++ code for quick sort.This procedure runs in O(n log n) time in average case. But in the worst case, It can take up to O(n^2) time.

     
    #include <iostream>

    using namespace std;

    void quick_sort(int[], int, int);

    int main()
    {
    int array[] = {4,7,3,6,9,2,8,5,1};
    quick_sort(array,0,8);
    for( int i = 0; i < 9; i++ )
    {
    cout<<array[i]<<" ";
    }

    return 0;
    }

    void quick_sort(int array[], int l, int h)
    {
    if( l < h)
    {
    int left = l; //starting index of the array
    int right = h;// ending index of the array
    int pivot = array[left];//take left most element as pivot

    while ( left < right)
    {
    //decrement right pointer as long as the element
    //at this index is greater than pivot
    while ( array[right] > pivot )
    right--;
    //increment left pointer as long as the element
    //at this index is less than or eqal to pivot
    while ( array[left] <= pivot )
    left++;

    //swap the elements if left and right do not overlap
    if( left < right)
    {
    swap( array[left], array[right] );
    }
    }

    //right is the correct position for pivot,
    //so swap the first element(chosen as pivot) with 'right'
    swap(array[l],array[right]);

    //recursively call quick sort for left and right parts
    quick_sort(array, l, right-1);
    quick_sort( array, right+1,h);

    }
    }

    How does a merge sort work?

    Merge sort follows the divide and conquer approach. This is also a comparison based sorting algorithm like Bubble sort, selection sort and insertion sort etc.

    In this method we divide the array into two halves. We recursively sort these two parts and merge them into single array. Here the base case for recursion is just one element i.e no need to sort an array with just one element.

    For example let us consider an array of 5 elements
    [3,2,1,5,4]

    It is divided into two sub-arrays [3,2,1] and [5,4]. We apply merge sort recursively on both the sub-arrays and merge them to become a single sorted array.

    Here is how the first sub-array gets sorted.
    [3,2,1] is divided into [3,2] and [1]. No need sort the second sub-array because it just contains one element.
    [3,2] is divided into [3], [2].

    The merge procedure combines the arrays [3], [2] into sorted sub-array [2,3].

    Then the sub-array [2,3] is merged with [1] to become [1,2,3]

    Finally [1,2,3] gets merged with [4,5] to become [1,2,3,4,5] which is fully sorted.

    The merge procedure works as follows. The input to the merge procedure is two sorted sub-arrays. 

    We initialize two pointers to the first elements of two sub-arrays. We copy the lesser element among them to a temporary array and advance the corresponding pointer to the next element. We repeat this procedure until atleast one of the sub-arrays becomes empty.

    Finally we copy the non-empty sub-array elements to the temporary array.

    Here is the Java implementation of merge sort. 

    public class Main {
    public static void main(String[] args)
    {
    int [] array = {51,126,98,12,3,34,269,73,6,88};
    mergeSort( array, 0, array.length-1);
    for( int i = 0; i < array.length; i++)
    {
    System.out.print(array[i] + " ");
    }
    }
    public static void mergeSort(int[] array, int left, int right )
    {
    if( left < right)// If the array has at least one element
    {
    int mid = (left + right) / 2;
    mergeSort(array, left, mid);
    mergeSort(array, mid+1, right);
    merge(array, left, mid+1, right);
    }
    }
    public static void merge(int [] array, int l, int m, int r)
    {
    //We need a temporary array of size r-l+1 for the merged elements
    int [] temp = new int[r-l+1];
    int i = l; //index of first sub-array
    int j = m; //index of second sub array
    int k = 0;
    while( i < m && j <= r)
    {
    if( array[i] < array[j])
    {
    temp[k++] = array[i++];
    }
    else
    {
    temp[k++] = array[j++];
    }
    }
    //copy if there are any elements remaining in any half
    while( i < m )
    {
    temp[k++] = array[i++];
    }
    while ( j <= r )
    {
    temp[k++] = array[j++];
    }
    //copy sorted elements from temp to original array
    for( i = l,j=0 ; i <= r; i++,j++)
    {
    array[i] = temp[j];
    }
    }

    } 
     
     

    This code runs in O(n log n) time in the worst case also. But it is not an in-place sorting mechanism because we use a temporary array in the merge procedure.