SKHeap; A quick MaxHeap and HeapSort implementation

Heap is an interesting data structure. It is a binary tree, that keeps the maximum (in case of MaxHeap) element at the root, thus providing access to it in O(1) i.e. constant time. You can pop the root element in O(lgN) time, and insert new elements into the heap in O(lgN) time as well. Initial buildup of the heap takes linear time. You can sort a sequence of elements using heap, by first building the heap out of all the elements, and then retrieve the elements back. Since initial build up is linear time, each retrieval of the maximum element is O(lgN) time, and you do N such retrievals, the resulting sorting algorithm is of O(NlgN) complexity and called HeapSort.

It is fun to implement these well known data structures and algorithms. So while I was bored and free for half an hour, I quickly wrote a basic implementation of a Heap and HeapSort in Objective-C and pushed it to Github. Check it out and let me know if you like it or find any issues with it.

Making all integers in an array same using minimum steps

In past rounds of both topcoder and codeforces, same problem showed up with slight variations. In generic terms, we had to make all integers in an array same, using minimum number of steps, where a single step is incrementing or decrementing a single element of the array by a constant integer, say ‘d’.

Solution:

We need to figure out median of the sorted array, set that as the target, and make all elements equal to this target. This will ensure minimum increments/decrements. When the number of elements in array “N” are odd, median is (N/2)th element of the array. If N is even, we have two medians, (N/2)th and (N/2)+1th element. We can choose any integer between these two medians (inclusive) as the target (given that selected integer is equal to other elements modulo ‘d’).

Remember that in order for a solution to exist, all elements in the array need to be equal modulo “d”. Because otherwise, no matter what number of increments/decrements your perform, integers can’t be equalized.

Explanation:

Why select median element as the target to make all other elements equal to?

Lets take an example: A = [2, 4, 5, 8, 9, 15, 35], d = 1

Here, median element is N/2 = 7/2 = 3rd element = 8 (0 indexed).

Lets start by deciding not to use median element as the target. Lets select another integer, ‘x’, as the target, which is not the median. It can be in either direction of the median, left, or right. In our example, let x = 4. Now lets say that the number of increments/decrements we had to perform to make all elements in given array equal to x, is ‘c’, the cost. Lets move our chosen target x closer to median by an element by incrementing by d, so that we now have one more element to the left, and one less on the other side. In our example case, let our new x = ‘5’. Now we have one more element to the left of our target, and one less to the right. Now in order to equalize all elements in our new array, which was equalized to our previous target of ‘4’, notice that we will have to add ‘d’ to all the elements to left of our target, and reduce ‘d’ from all elements to the right. Since number of elements to the left is 2, and there are 4 elements to the right. our cost ‘c’ is reduced. We can keep on going like this, till we reach the median as our target ‘x’. Once we have chosen median as our target ‘x’, we obtain an optimal cost ‘c’. Going either to left or right of it, only increases our cost.

Sieve of Eratosthenes: Finding all primes below a limit N

In number theoretic algorithmic problems, there arises cases where you need to find all primes below a certain limit, say N. The improved trial division primality check algorithm can be used to find all primes below a certain limit that isn’t too large. But with larger limits, there is a need for a more efficient way. Sieve of Eratosthenes is a 2000 year old algorithm for doing just that, in an efficient manner.
Continue reading

Faster algorithm for primality test

Prime numbers are those positive integers that are divisible only by 1, and itself. For example 2 is a prime number. So are 3, 5, 7, 11, 13, and 17. All of these have exactly two divisors, 1, and the number itself. 1 was considered as a prime for a long time, before it was declared to be not a prime.
Continue reading