Irreal

The other day, I presented two Elisp coding challenges. I specified Elisp because Irreal readers tend to like Emacs related posts. The down side of that is that several of you worried about bignums and other Emacs limitations. That wasn’t my intent—I just thought the problems were interesting and might even come in handy someday in an interview.

In any event, here are my solutions. All the commenters who gave an answer for problem 1 (Given a list of integers from 1 to n but with one of the integers missing, write an efficient algorithm to find the missing integer.) gave the same O(n)/O(1) algorithm for time/space, namely just sum the integers up and subtract the sum from (n² + n) / 2 to find the missing number.

The solution to the second problem (Given a list of integers from 1 to n but with one of the integers missing and another repeated, find an efficient algorithm to find the missing and repeated numbers.) is similar except the we sum the numbers and their squares. If we let delta₁ be the difference between the sum of the integers and the sum of the integers from 1 to n, and delta₂ be the difference between the sum of the squares of the integers and the sum of the squares of the integers from 1 to n, we have:

• repeated – missing = delta₁ and
• repeated² – missing² = delta₂.

From there, some very easy algebra (the quadratic terms drop out) we get

• repeated = (delta₂ + delta₁²) / 2 delta₁
• missing = (delta₂ – delta₁²) / 2 delta₁

Now it’s easy to write an algorithm that’s linear in time and constant in space (modulo some increase in size for bignums if we’re using a language that supports them).

(require 'cl)
(defun solve (n repeat missing)
  (let ((numbers (cons repeat
                       (delete missing (loop for i from 1 to n collect i))))
        (sum-1-to-n (/ (* n (1+ n)) 2))
        (sumsq-1-to-n (/ (* n (1+ n) (+ n n 1)) 6))
        (units 0)
        (squares 0))
    (dolist (i numbers)
      (incf units i)
      (incf squares (* i i)))
    (let ((delta1 (- units sum-1-to-n))
          (delta2 (- squares sumsq-1-to-n)))
      (message "repeated number is %d, missing number is %d"
               (/ (+ delta2 (* delta1 delta1)) (* 2 delta1))
               (/ (- delta2 (* delta1 delta1)) (* 2 delta1))))))

I didn’t bother to randomize the list because I don’t make any use of the fact that it’s (almost) in numerical order. Some readers calculated the length of the list but I assumed that n was given as part of the problem. If not, it’s simple to count them up as we sum the numbers and their squares and then calculate sum-1-to-n and sumsq-1-to-n afterwards.

When we run solve, we get the expected answer

ELISP> (solve 100 35 78)
"repeated number is 35, missing number is 78"
ELISP> 

I ran across a couple of nice interview questions and an interesting story over at Tanya Khovanova’s Math Blog. The two questions are:

1. Given a list of integers from 1 to n but with one of the integers missing, write an efficient algorithm for finding the missing integer.
2. Given a list of integers from 1 to n but with one of the integers missing and another integer repeated, write an efficient algorithm for finding the missing and repeated integers.

In both problems the numbers in the list are in no particular order.

So the challenge is to write the two algorithms in Emacs Lisp. The interviewer expected a O(n log n) algorithm for time for the second problem. Can you do better?

Don’t go over to Khnovanova’s blog until you have solved the problems because there are spoilers in the comments. After you solve the problem, though, be sure to read her story about “hiring the smartest people in the world.”