# 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.