## Everybody hates Haskell

Anecdote time: this Monday we had a presentation at the university – a US software company (no need for names) has vacant places for programmers and developers. On one of their posters I found an interesting challenge problem (solve the problem and get a job)

First n positive integers are randomly placed in an array of length n. One of integers does not appear in the array – instead of it, one of the integers in the array appears twice. What is the simplest algorithm for finding the number omitted and the number repeated in the array without sorting it?

Minute I read it, I got the half of the solution – but the other half puzzled me for 15 minutes or so. I was on my way home when it struck me – I got it! Then I just turned 180° and went back. I reported the solution to their representative – it was indeed the one they expected. Now, during the Q&A session he asked the students in the room what is their favorite programming language. I answered honestly: Haskell. He just smiled. After 10 minutes a colleague of mine asked him whether the company would finance PhD for their eventual employees. “Yes, but we need to know what they plan to study. We won’t finance them if they want to get a PhD studying Haskell, for instance”.

Darn.

P.S. I didn’t want to spoil the fun of algorithm making to my readers by writing the solution for the problem given above. Still, if you get stuck, the solution is written under this post, white font color (select it to see it).

If you sum first n positive integers and subtract the sum of all numbers in the array, the result is x-y where x is the number omitted and y is the number doubled. On the other hand, if you divide the product of first n positive integers with the product of elements in the array, the result is x/y. Two equations, two unknowns, you’re done. In order to save time, don’t multiply and sum the elements in different loops, take just one loop, before that initialize D=0, Q=1 (D for difference, Q for quotient) and in a for loop with counter i going from 1 to n make D=D+i-array(i) and Q=Q*i/array(i).

My solution is: first step the same as yours, to get x-y; then sum the squares of first n integers and subtract squares of elements of array, to get x^2-y^2. A simple division gives x+y, and the rest is easy.

That’s a good one – since my way could cause some inaccuracies for very large arrays due to rounding in the division process in each iteration, your solution is safer.