dmorin's Journal: Programming Puzzle

Ok, one of my guys at work brought this one in a few weeks ago, and now that I've been told I'm gonna be given a similar test I thought I'd post it.

You have an array of 1..N-1 randomly sorted integers in which one of the sequence is missing. Got that? So if N=3 you might have 1,3 and 2 is missing.

The challenge is to determine, in as efficient a way as possible, which number is missing. Give you a hint, the answer doesn't involve sorting the numbers at all.

An answer

[cyranoVR]

But I'm guessing the answer is something like this

1) Come up with a formula that produces the sum of any sequence of numbers (1,2,3...N). I remember studying this in highschool.

I think the formula is y = 1/2(x^2 + x)

2) Find the actual sum of the number list.

3) Compare the sum of the list with the expected sum from (1)

The difference should reveal what number is missing.

class BoringMathProblem {
static int findMissing (int n[]) {

int x = n.length

int expectedSum = .5 * ( (x^2) + x) )

int actu

Re:An answer

[dmorin]

Yup, that'll do it. Although I do have to take off some points for forgetting a bunch of semicolons. :)

See what you think of this one, which has no multiplication or division, or floats.

for (int i = 0, sum = 1; i < n.length; i++) {
sum += (i+2)-n[i];
}
return sum;

The semicolons

[cyranoVR]

I always forget the semicolons. What do expect from a VB programmer? :)

Also, it seems you're right - you would have to add a cast to the line with the expectedSum as follows:

int expectedSum = (int)( 0.5 * ( (x^2) + x) ) )

However, I like using this approach rather than a loop, as I would like to think it is more efficient than using a loop to add up the problem array. Wouldn't it be fun to do some testing to see which approach is better? I bet that your approach is faster for short lists, but for lis