Let’s look at a simple problem if figuring out if a given number is a prime number or not? And how best we can compute it.

A prime number is a whole number greater than 1, that are only divisible by itself and 1.

A naïve approach is to check if the number is divisble by all the numbers starting from 2 to itself. We start from 2 as it is our first prime number.

bool is_prime(int n) {
  for (int i = 2; i < n; i++) {
    if (n % i == 0)
      return false;
  }
  return true;
}

But, can we do better? Notice that we need to check for numbers only less than or equal to the square root, say sq of the given number n to be tested. If there’s a number that divides n and which is greater than sq, the result of that division would be a number less than sq. For example let’s say n = 26 and we want to figure out if n is prime. We are claiming that we need to check only until the square root of 26 - rounded down to 5. Let’s pick a number that divides 26, say 13 and this number on dividing 26 yields 2. So when we start to check from 2 to 5, we would have already figured out that it is divisible by 2 and is not a prime. We just ran into another beautiful fact:

there are no even primes greater than 2

That would let us optimize our loop further - if we initially checked whether n is not 2, we would check only every other (odd) number to see if it divides.

bool is_prime(int n) {
  if (n <= 1) return false;
  if (n == 2) return true;
  if (n % 2 == 0) return false;
  int m = (int)sqrt(n);
  for (int i = 3; i <= m; i+=2) {
    if (n % i == 0)
      return false;
  }
  return true;
}

Primes are beautiful. Hopefully, I will write more posts on them in future.

Let’s look at another simple, interesting problem:

Given a sorted array, with no duplicates, that has been rotated (also called circularly sorted array), find out the number of times it has been rotated

For example, [2 3 5 8 11 12] is a sorted list of numbers and if we rotate it twice, we end up in [11 12 2 3 5 8]. We are required to find the number of times it has been sorted, looking at this list. The straight forward way is to look for the minimum element of the array and the index of the mimimum element gives us the number of times it has been rotated. In this case 2 is the minimum element and the index of the mimumum element is 2 (indices start at 0 in most of the languages we use here). The time complexity would be O(n) as we need to traverse the array looking for the mimimum element.

Can we do better? Can we use a nice property of circularly sorted arrays (lists)?

For the element we are looking for, call it the pivot element, both the left and right neighbours are greater than the pivot element. This is the only element in a circularly sorted array with this property.

So, our goal is to find the pivot element. We already know that the array has been sorted - so we can use binary search to look for the pivot element. We compute the middle element of the array, call it mid and search in the left and right halves of the middle element. Let’s call the lower index low and higher index high for the purposes of computation. So, we compute the middle element as mid = (high - low) / 2. The neighbours of this middle element, called prev and next are computed as prev = (mid + 1) % n where n is the size of the array (since it is circularly sorted we need to wrap around and hence we do this modulo n operation) and next = (mid + n -1) % n. Now, if mid turns out to be our pivot element, i.e. we check for pivot property, we are done - we just return mid as the result. Otherwise, we keep moving low and high to decide which half of the array we want to search for the pivot element. Recollect that we know the array is (circularly) sorted and this makes our job easier. For example, if the element at mid is less than the one at high we can deduce that the right half of the array is sorted, and so we adjust high to be mid - 1 (i.e. make left half our focus of pivot element search).

int rotation_count(int A[], int n) {
  int low = 0;
  int high = n-1;
  int mid = (high - low) / 2;
  int next, prev;
  while (low <= high) {
    if (A[low] <= A[high])
        return low;
    next = (mid + 1) % n;
    prev = (mid + n - 1) % n;
    // check pivot element property!
    if (A[mid] <= A[next] && A[mid] <= A[prev])
        return mid;
    else if (A[mid] <= A[high])
        high = mid - 1;
    else if (A[mid] >= A[low])
        low = mid + 1;
    }
}

Isn’t it interesting? That’s all for now!

Let’s take a quick look at a simple problem:

Given a list of numbers, how would you determine the maximum pairwise product of numbers in the list?

For example, if we have the list [1; 3; 5; -2] the maximum pairwise product is 15, which is the product of 3 and 5.

The straigt-forward approach is to compute all possible pairwise products and identify the maximum among the intermediate results:

long long MaxPairwiseProduct(const vector<int>& numbers) {
  long long result = 0; // result to hold the max pairwise product
  int n = numbers.size();
  long long product = 0;
  for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
	  product = (long long)numbers[i] * numbers[j]; 
	  if (product > result)
		result = product;
	  }
	}
  return result;
}

Since we have two loops that iterate over the list of numbers, the time complexity is O(n²).

Can we do better? Yes, we can. The idea is to find the maximum and the second maximum elements in the list - and their product would be the maximum pairwise product.

long long MaxPairwiseProductFast(const vector<int>& numbers) {
  int n = numbers.size();
  long long product = 0;
  // find the max element in the collection 'numbers'
  int max_index1 = -1;
  for (int i = 0; i < n; i++) {
    if ((max_index1 == -1) || (numbers[i] > max_index1)) {
	  max_index1 = i; // largest number in the list
	  }
  }
	
  int max_index2 = -1;
  for (int j = 0; j < n; j++) {
    if ((numbers[j] != numbers[max_index1]) && ((max_index2 == -1) ||
	  (numbers[j] > max_index2))) {
	    max_index2 = j; // second largest number in the list
	  }
  }
	
  product = numbers[max_index1] * numbers[max_index2];
  return ((long long) product);
}

Simple and sweet!

In one of our [earlier posts] we saw how to eliminate consecutive repetitions in a list. Let’s refresh our memory and take a look at the compress function we saw earlier:

let rec compress lst =
  match lst with
  | [] -> []
  | x1 :: (x2::x3 as t) ->
     if (x1 = x2) then compress t
     else x1 :: compress t
  | smth_else -> smth_else;;

This is a straight forward recursive function. Let’s first rewrite it using auxiliary function.

let compress lst =
  let rec aux acc l =
    match l with
    | [] -> acc
    | x::[] -> x::acc
    | x1::(x2::x3 as t) ->
       if (x1 = x2) then aux acc t
       else aux (x1::acc) t
  in
  List.rev(aux [] lst);;

I think it is pretty straight forward - if we see repetition (x1 = x2) we ignore the element and call the auxiliary function on the remaining part of the list. (Note that we do not eliminate x2 as we want to retain a copy of each repeating element).

Today, we shall not eliminate, but collect the consecutive repeating elements into sublists. For example, if we have the list [1;1;1;2;2;3;4;5;5;6;1] we want to make it into this list [[1; 1; 1];[2; 2];[3];[4];[5; 5];[6];[1]]

We will again use recursive calls to auxiliary function, very creatively called aux. Apart from keeping track of repetitions, we also need to collect them into sublists. So, in this case, as we traverse the input list and process element by element, we will collect the repeating ones in a sublist and collect the ones that are not consecutive repetitions in another (as this will also be a part of our final result). We know that we usually return the accumulator as the result - so in this case, we may want to maintain two accumulators - one cur to collect the consecutive repeating elements, and another acc to collect the remaining.

• When we encounter repetitions, we will push the repeating entries into cur sublist
• When there are no repetitions, we will keep merging cur with acc and eventually return acc as the result.

let pack lst =
  let rec aux cur acc l =
    match l with
    | [] -> acc
    | [x] -> (x::cur)::acc
    | x1::(x2::x3 as t) ->
       if (x1 = x2) then aux (x1::cur) acc t
       else aux [] ((x1::cur)::acc) t
  in
  List.rev(aux [] [] lst);;

In both the compress and pack functions that use auxiliary function, we reverse the result using OCaml List module’s built-in rev function.

Food for thought - why is the result getting reversed? If you work out a small example, it would become apparent.

That’s all for today. Enjoy your weekend!

By now, we are all pretty comfortable with recursive functions, using auxiliary functions, etc. Let’s now put these skills to write merge sort algorithm in a recursive fashion. We need the following three ingredients to prepare our recipe

• split function that would take a list and split it into two lists
• merge function that would merge a pair of sorted lists
• merge_sort function that would use the above two to build the sorted list recursively.

Let’s prepare the above one by one. First, the split function that takes a list lst as input and splits them and returns a pair of lists as output. The moment we see that we need to return two lists (a pair of lists) as output, intuitively we can imagine that we would need two accumulators, let’s call it a1 and a2. Next, we will think about the possible cases (patterns).

1. The base case is going to be empty list as input in which case our result would be two empty lists (the two accumulators we use).
2. If we pass a list that has a single element, one of the lists we return would contain this single element and the other would be an empty list (remember, we need to return two lists as result).
3. If there are multiple elements, like any reasonable list, we would pick the first element and push it into the first accumulator, the second element into the second accumulator and then recursively call the auxiliary function on the rest of the list.

So, this is what it looks like - you can match the three items above to the three patterns in the code fragment below - pretty straight forward.

let split lst =
  let rec aux a1 a2 l =
    match l with
    | [] -> a1, a2
    | [x] -> x::a1, a2
    | x1::(x2::x3) ->
       aux (x1::a1) (x2::a2) x3
  in
  aux [] [] lst;;

Now, let’s prepare the second item in our list - the merge function. This is just pattern matching and even simpler than our split function.

let rec merge (lst1, lst2) =
  match lst1, lst2 with
  | [], l -> l
  | l, [] -> l
  | (h1::t1 as l1), (h2::t2 as l2) ->
     if (h1 < h2) then h1 :: merge (t1, l2)
     else h2 :: merge (l1, t2);;

Finally, let’s prepare the merge_sort function that takes a list lst as input. First we would split the input list into two lists using our split function. Then, we would recursively call merge_sort on the two sub-lists (result of split function) and merge the results of these recursive calls using our merge function. Again, the base case is the empty list and another possibility is an input list with a single element - both are straight forward.

let rec merge_sort lst =
  match lst with
  | [] -> []
  | [x] -> [x]
  | l -> let l1, l2 = split l in
         merge (merge_sort l1, merge_sort l2);;

That was a very intuitive way to write a merge sort algorithm. Hope you all agree with me!