Prime number pairs summing to an odd number

While reading a book (details below), I came across a very nice problem as follows.

Find all pairs of prime numbers that sum up to 999.

As the book says, it involves thinking before actually attacking the problem. Few observations:

• Sum given is odd (999).
• To get sum odd, exactly one of the two numbers have to be even.
• Asked are the pairs of prime numbers.
• Meaning, we want intersection of prime and even which is just the number 2.

So, one of the numbers has to be 2; and thus the other of course is 997. And, that's the only pair of prime numbers which sums up to  999.

Cool indeed! :)

Book details:
Title:  math Charmers - Tantalizing Tidbits for the mind
Author: alfred s. posamentier
Publisher: University Press

n-th last element in the list

Given a singly linked list, find n-th element from the last.

The most obvious way is to traverse the list once and get its length say L. Then traverse again first L-n nodes to get to the n-th last node. This is linear in complexity but we need to traverse the list twice. Can we eliminate this?

We can, using extra pointer. Let's have a pointer to the list say *first and one more say *second. We traverse the list using *first till n nodes are traversed. Now imagine that at this moment we start traversing the list with second pointer, say *second. Then, by the time *first reaches towards the end of the list, *second will fall short by n nodes from the end of the list. That's precisely the node we want - n-th node from the end. So the solution is clear. After *first reaches the n-th node, start traversing with *second and continuing with *first till *first reached the last node.

Note: This will take care of the error in input when n > length of the list as *first will reach NULL sooner than expected.

Must Read

This post will be kept updated with links as and when I find them. While browsing, if you come across any of the dangling / dead links or redirections, please let me know.

- A collection of dynamic programming
problems very well explained.

for loop in C

Following code has a bug. Can you find that out? Hint: Well, this code is intended to print "hi " **20** times, does it?
   int i, n=20;
   for (i=0; i < n; i--) {        printf("hi ");    }

If you have found the bug, can you now make it print "hi " 20 times by replacing one character.

Well, the answer is too simple (once known :D). Just a hint: Make sure you understand how for loop works, specially at the beginning of the loop.

(Spoiler alert: Solution in comment)

Maximum contiguous subsequence

Given an array of N numbers (positive, zero, negative), find maximum contiguous subsequence i.e. a subsequence which is contiguous and which has maximum sum i.e. mathematically, sum of k elements A[k] where k ranges from i to j, such that 0<=i<=j<=N-1, is maximized.

Let's take an example. If A is {2,4,1,5,6,7}, well! the answer is the whole array itself. And that's why we need to consider a generalized case in which the array contains positive as well as negative elements. Similarly, for the array A={-2,-10,-9,-1}, the sum better be zero than negative and the the answer is empty subsequence. Thus, these two are degenerate cases.

Now, let's consider the general case. We can come up with a trivial algorithm as follows. We want to find a subsequence of the form 0<=i<=j<=N-1, thus we can straightaway write 2 loops as follows.

for i=0 to N-1
       for j=i to N-1
             keep sum of A[i] through A[j], keep track of max sum seen so far and corresponding i and j values
       end for
end for

As one can see, this is O(N^3) algorithm. If you think it's O(N^2), please take a look at the step in which we compute the sum. This sum needs to be computed over all subintervals and thus it causes another for loop, giving rise to the complexity of O(N^3).

Now, of course the question is - Can we do better? We can definitely do this in O(N^2) as you must have realized by now. (I took quite a lot of time to get to this :D) Basically, we can eliminate the innermost loop over K using following fact. If we denote sum of A[i] through A[j] as Sum(i,j) then we can write
       sum(i,j+1) = sun(i,j)+A[j+1]
Thus, we need not go through all values again and we save one loop here, thus getting O(N^2) complexity.

We can still do better btw! At this moment I myself asked a question - how much better? Can we go sub linear? And I think, we cannot. The reason is - as the input array is not sorted or in any order, we cannot judge for more elements based on small number of elements. Remember what we do in binary search - comparison with one element at the middle (small number of elements) gives us an indication of half of the array (more number of elements) being useless for further steps. Such indication we cannot get here and thus we HAVE TO look at EVERY element at least once and as we will see - also at most once! Thus, we cannot hope for sub linear complexity but it has to be linear.

The algorithm, which I am not writing here is of the complexity O(N). It can be arrived at by two different methods. The underlying principle is the same for both the methods. The hints for the two methods are as follows. I think, if you get one of them, the other one will be trivial.
1. Biggest hint for method 1: The array contains negative elements too and any negative sum is worse than sum=0
2. If you have solved this by method 1, then this hint may be redundant: Use dynamic programming

nJoy!! :)

Rotated sorted array

Part A: Given a sorted array which is rotated either to the left or to the right by k positions (0<=k<=n-1), find the maximum element. Trivial solution:
Check for each possible k, whether it is the maximum element by checking adjacent values i.e. a[k-1], a[k] and a[k+1] circularly (meaning, for k=0, check a[n-1], a[0] and a[1]). This is obviously O(n) due to k's range and because 3 comparisons per k can be considered as O(1) being constant time access to array elements. Thus, of course we aim at sub linear time.

So the main issue is - how to reduce problem size so that we solve smaller and smaller problems, discarding some part of the input and get quickly to the problem of size small enough (ideally 1). What if we have the middle element, i.e. a[m]? In order to decide which part to discard, one must be able to visualize the rotated sorted array, which is shown as follows. Let the new index of maximum element be k.


Now, one can see that m will always lie on upward slope and thus slope trick will not work. But, we can now distinguish between left and right part around k as follows. If m<=k, m will always be more than the first element in the rotated array, because the sorted order is retained. Thus, by comparing a[m] and a[i], one can easily decide which part to throw. If a[m] >= a[i] we can throw left half else right half. Once we reduce problem size to 1, m and k collide. This works in O(log n).

Array with a mountain shape

Given an array in which initially elements start increasing till some index k and then they decrease. Find k.

Of course this asks us to find k in sub linear time. Otherwise, the most obvious solution is to check every element till elements increase and then at first drop in value, you get k. Sub linear acts as a hint for logarithmic. Logarithmic gives hint for dividing and throwing away some part, so that we reach a singleton or small enough set quickly. Let's see whether we can discard some part of the array. What if we pick the middle as we do in binary search? This gives us m=(i+j)/2 and m<=k or m>k. If we can somehow establish this relation between m and k (note: k is unknown, we have to find it), we can throw away the remaining part. How can we do this then? We know that k is the index such that on its left, the line plot of the array is ascending and on its right, it is descending. This means, if we are on left of k, we are on upward slope as against when we are on the right part of k. This hint is enough I guess. Once we get m, check a[m-1], a[m] and a[m+1] to get an indication about the region of slope where m belongs to, by comparison. Once we know that we are on upward slope, we know that m<=k, so we discard this part. Similarly for the case when m>k. Once we reduce problem size from n to n/2 at every iteration, we are in logarithmic space. Thus the algorithm performs in O(log n).