Close

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

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

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

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

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

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

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