## Find ‘k’ smallest numbers from a million numbers (and take the girl with you!)

Your mum just told the “aunty next door”, the obese mother of your 6-year-crush “girl next door” that you are extremely smart and good in Math. WTF, mom?! And aunty being the crook she is, gives you her shopping list which has 1000 products with their prices and asks you to pick the least-values 10 products. Your crush is right there. If only you were in the Matrix, right?

Scale out the problem to finding the k smallest numbers from a million numbers and throw in a computer to solve the problem with code. What now? How do you go about it?

Well, you can** sort all elements in O(n log n) time** and pick the first k numbers. But can’t you try and be a little smarter? Even the girl knows basic sorting!

Maybe try and find a **worst case O(n) complexity algorithm**? Oh, stop staring! So here is the magic mantra: **Hoare’s Quick Select **algorithm.

In this algorithm,** we use the technique of Partitioning from Quick Sort** to get what we want. Partitioning basically takes a pivot element at random, puts it in its right place and puts all numbers lesser that the pivot to one side and the rest on the other. *So if we are able to get the “k”th smallest number as the pivot, we are done!** *(as we can then pick the whole partition with k elements as our answer)

1. Start with a random pivot. Iteration number = 1 for the first time.

2. Partition the array. Takes O(n/iteration number) time.

3. If the pivot is placed at the kth position (relative to original array), we are done! Else, first increment Iteration number. Then : If it is placed before the kth position, go to step 2 with the right hand partition as the array. Otherwise go to step 2 with the left partition.

Got the point? This can be a very helpful method to solve problems such as k largest or smallest element, etc.!

Now to **prove time complexity O(n) in worst case**. Since we process just one partition each time (as opposed to processing both partitions like we do in Quick Sort), here is how the effort looks –

**Effort = n + n/2 + n/4 …**

We know that **1/2+1/4+1/8+… = 1**, (can prove it too)

Hence,** Effort = n + n = 2n = O(n)**

Tada! 🙂

## Find the element which occurs > n/2 times in an array with n elements

Guess what? The Election Commissioner just called upon you to count the **10 billion votes** and find out the person who has majority votes! You are flabbergasted! You had a weekend of good sleep planned out with snack breaks every 2 hours and now you are stuck with this grunt work! **However,** **the EC ensures you that the one who wins will have more than half the total number of votes!**

If you think of **keeping a counter** for each of the (assume **(5 billion – 1) candidates**) and then go on to find the one with the maximum number of votes by incrementing counts, well you can forget the next 3000 weekends and say goodbye to your sleep.

And if you have the brilliant idea of **sorting the votes in some order** and getting the answer, you might just want to find one of those supercomputer’s access key.

What you should notice is that more than half the votes are for the winner. This can be solved using **Moore’s Voting algorithm in O(n) time with constant space**. Here is what you do.

1. Take two variables,current_candidateandcount(which corresponds to count of current candidate)

2. Set count to 0 initially.

3. Now everytime you find the count to be 0 (even at the beginning), make the current element as thecurrent_candidate.

4. Move forward in the array. If you find element the same as current candidate, increment count. If not, decrement count.

5. If count is 0, go to step 3. Else, move forward in the array

6. After traversing the whole array you’ll be left with the majority vote as thecurrent_candidate.

Bam! Want an example?

**B B C G H B B B T**

*Start with* candidate = (none), count = 0

First is a B, candidate = B, count = 1

moving forward, another B, candidate = B, count = 2

now a C, candidate = B, count = 1

and a G, candidate = (none), count = 0

now an H, candidate = H, count = 1

now a B, candidate = (none), count = 0

and another B, candidate = B, count = 1

and one more B, candidate = B, count = 2

and finally T,** candidate = B**, count = 1

Hence, you arrive on the answer candidate –> B !

Weekend plans to sleep might still pan out, eh? Cheers! 🙂

## Given N numbers, find pairs with difference K

*Problem Statement :* You have been given N numbers and a value K. Find the number of pairs in this given list of numbers whose difference is exactly equal to K.

This is a very simple one. Trying a brute force over all the elements is not being efficient. So what we’ll do is that we’ll sort the input array and apply a fine-tuned brute force as follows.

Once the array is sorted, for every number at position j, you start checking numbers backward from j to 0 (let us say using variable i, where i<j) and skip to checking for j+1 if the difference of the jth and ith element exceeds K. If you find their difference to be exactly K, you increment your count.

A very simple implementation of sorting. 🙂

## Spiral traversal of a matrix

Duh! This is a no-brainer. But since it might be useful to select few out there, here goes.

*Problem Statement:* You have a 2D matrix. Print its elements while traversing in a spiral manner.

Example –

1 2 4 6

5 3 8 9

4 5 6 7

9 6 4 1

Now your output should be of the form,

1 2 4 6 9 7 1 4 6 9 4 5 3 8 6 5

( You get it, right? )

So all you need to do is

0. increase COLUMN, “N” times (for a NxN) matrix

1. increment ROW, N-1 times

2. decrement COLUM, N-1 times

3. decrement ROW, N-2 times

4. increment COLUMN, N-2 times

5. (Repeat the process)

That is it! Next one will be a toughie. Gear up! 🙂

## Sub-sequences (ICPC 2011 Amritapuri Online Contest)

*Problem Statement:* You are given a sequence of N numbers A[1..N]. Consider a sub-sequence (of continuous or non-continuous elements in the same order as given) such that the bitwise AND of all the numbers of the sub-sequence is equal to the bitwise OR of all the numbers of the sub-sequence. Amongst all such sub-sequences, find the sub-sequence that has the maximum sum of the numbers, and print this maximum sum.

Limits: 1<=A[i]<=10000

Hmm. So what are your first thoughts? You want to traverse over all the sub-sequences? Wrong! That would take hell lot of time. We’ll do it in O(n). All you need to do is pay attention to the properties of the bitwise AND and bitwise OR operator. These are two mutually exclusive operators. By using this term here, I mean to specify that *no two different numbers can have the same result after their OR or AND*. You can prove this by taking a few examples (Exercise left to you 😛 )

So the only AND and OR operations to satisfy the equality conditions can be performed on the same number itself. Your subsequences are thus reduced to those having the same number (and its duplicates). Hence, you can simply do the following :

1. Find number of occurrences of each element in the array, store it is OCCURRENCE[i] (corresponding to number i )

2. Find the maximum value of OCCURRENCE[i]*i by scanning through all the array positions.

This maximum value is your answer! 🙂 Once again, note why sub-sequences of duplicates are being made. It is because of the condition that AND of the subsequence should be equal to their OR.

It was an easy one but showed a nice Bit Manipulation property. 🙂

## Find the depth of a tree without using recursion

In my last post, I discussed how to find the depth of a tree *using* recursion. Now I’ll point out the way of doing this without using recursion. I hope everyone knows what a Breadth-First Search (BFS) is. To explain it in short, you add all the child nodes of root in a queue. Then you pop a node out of the front and add the child nodes of that to the end of the queue. In this way, you traverse a tree in a Breadth-First manner.

Similarly, all you need to do is add a random value “X” to the queue once you have added the children of root. Now start popping and proceed with BFS. When you encounter the “X”, you add another “X” at the end of the queue and increase the value of depth (initially 0). In essence, every “X” occurs after you have added the nodes at one level. So your depth variable ends up having the number of “X”es or depth of the tree at the end of your program when your queue is empty. 🙂

Here is the algorithm (in words) to make things clearer,

1. Add ROOT to queue

2. Pop ROOT, Add its child nodes to queue, Add “X” to queue

3. Pop elements from queue. (If not “X”, add its child nodes to the queue, else, add “X” to the queue and increment depth)

4. Go to Step 3 till queue is NOT empty.

You have it! The depth of your tree in time complexity O(V+E). This method is useful when you don’t have a lot of memory to use and can’t afford to load the memory stack through recursion.

See you soon!