Solution to the Two Challenges

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 (n2 + 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 delta1 be the difference between the sum of the integers and the sum of the integers from 1 to n, and delta2 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:

  • repeatedmissing = delta1 and
  • repeated2missing2 = delta2.

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

  • repeated = (delta2 + delta12) / 2 delta1
  • missing = (delta2delta12) / 2 delta1

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> 
This entry was posted in Programming and tagged , . Bookmark the permalink.

2 Responses to Solution to the Two Challenges

  1. Jorge says:

    I was about to post my solution when I saw that you just posted yours. I use exactly the same formulas, but computed the differences at each step, this allows for bigger numbers without overflowing.

    It also is pure elisp. It uses recursion, so I don’t know if it still O(n), the FOR equivalent would be, but recursion feels more “lisp”. In case someone is interested:
    http://pastebin.com/pe21gT80

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>