Find the duplicate

You are given an array of 2n + 1 numbers. Out of these 2n + 1 numbers, 2n are duplicate. You are supposed to find the number which is not duplicate.

Inroduction to Statistics

Statistics is a commonly used word and also a commonly misunderstood one. Statistics in its full scope encompasses collection, organization, summarization, presentation, analysis of data, drawing valid conclusions and taking actions based on it. In this way, statistics provide a concrete and axiomatic way approach of interacting with our environment based on the observations. At the core, statistics is merely commonsense defined axiomatically, so that you don't require commonsense to understand commonsense.

In a more restrictive sense, statistics means the observations and numbers derived or based on the observations. Observations are also referred as data so we can regard statistics as data and the number based on the data.

We however prefer the former definition of statistics as it clearly highlightsnot only the means but also the ends of the statistics.

Breaking into pieces

You are given a iron rod, whose weight is 40 kg. You are supposed to make four pieces such that employing only those four pieces and a weight balance, you should be able to weigh all the integral weights from 1 to 40. What are the four weights ?

The problem is an interesting one and involves a subtle application. Please do not come up with a solution devised by combinatorial exhaustion of choice because as an adversory I can introduce heavier iron rods, which will sink the ship of combinatorial exhaustion.

Fiddling with for statement

At times fiddling with C programs and syntax can be real fun. Following is a simple program in C, which currently is not working

#include <stdio.h>
int main(int argc, char *argv[])
{
    int i, n = 20;
    for ( i = 0; i < n; i--)
        printf("-");
    return 0;
}

You can change one character in the above program to make it working. There are three such solutions existing. So have fun with the C syntax and more than one way to accomplish task.

Black and White Heads

Mathematical Induction is one of the powerful techniques for proving a conjecture for countable infinite sets. Below is one classic example of a problem, which is solved using mathematical induction arguments. The problem is from classic book on discrete mathematics, Elements of Discrete Mathematics (Mcgraw-Hill Computer Science Series). The problem goes as follows -

The king summoned the best mathematicians in the kingdom to the palace to find out how smart they were. The king told them: "I have placed white hats on some of you and black hats on the others. You may look at, but not talk to, one another. I will leave now and will come back every hour on the hour. Every time I retur, I want those of you who have determined that you are wearing white hats to come up and tell me immediately". As it turned out, at the nth hour every one of the n mathematicians who were given white hats informed the king that she knew she was wearing a white hat. Why ?

There are several variations of the above problem but the underlying theme is same. The solution for the above problem is given in the book whose link is given above. The problem is a fantastic application of the use of mathematical induction in proving certain conjecture. In our problem, the conjecture is at nth hour all the mathematicians wearing white hats will know about it.
Such types of proofs occur commonly in the computer science and mathematics domain. In all such situations, we have a set having a certain property and we wish to prove a conjecture over the given set.

Single Pass Palindrome Determination

We are supposed to give an algorithm which would determine whether the given input string is a palindrome or not. However there are certain constraints on the algorithm. The constraints are as follows -

• You do not know the length of the input string
• You can read each character of the input string only once (I think that the implication of this constraint along with the previous should be clear to everyone)
• You have to employ constant space

Now you have to come up with an algorithm and if you claim it to be the best then a proof for the same.