{"id":189,"date":"2011-08-04T14:11:00","date_gmt":"2011-08-04T18:11:00","guid":{"rendered":"http:\/\/irreal.org\/blog\/?p=189"},"modified":"2011-12-27T13:03:03","modified_gmt":"2011-12-27T18:03:03","slug":"sum-of-two-integers","status":"publish","type":"post","link":"https:\/\/irreal.org\/blog\/?p=189","title":{"rendered":"Sum Of Two Integers"},"content":{"rendered":"\n<p>A couple of days ago, I wrote about <a href=\"http:\/\/irreal.org\/blog\/?p=183\">upgrading to Clozure Lisp 1.7<\/a> and remarked that I should try it out with a miniproject, perhaps from <a href=\"http:\/\/programmingpraxis.com\/\">Programming Praxis<\/a>. I went over there and found the <a href=\"http:\/\/programmingpraxis.com\/2011\/07\/19\/sum-of-two-integers\/\">Sum of Two Integers<\/a> problem, which looked interesting. The problem is given a list of integers and a target integer determine if there are two integers in the list that sum to the target. <\/p>\n<p> I chose to interpret the rules strictly: <\/p>\n<ul>\n<li>You can make no assumptions about the list of integers. They could   be positive, negative, or zero. Numbers might be repeated multiple   times. They are not sorted and you do not know the maximum or   minimum number without checking the list. <\/li>\n<li>Similarly, you can make no assumptions about the target number other   than that it&#8217;s an integer <\/li>\n<li>You must find exactly two integers that sum to the target   number&mdash;you can&#8217;t reuse a number or just find the target in the   list. Thus, if the target is 10 and 5 is in the list, there must be   another 5 in the list for (5, 5) to be a solution. Similarly, if 10   is in the list, that&#8217;s not a solution unless 0 is also in the list. <\/li>\n<\/ul>\n<p> Truth to tell, if this were a one-off most of us would just hack up the obvious n<sup>2<\/sup> solution with two nested loops checking each pair of numbers in the list. Of course, none of us would admit to doing such a thing so the question is: can we find a better solution? My first thought was to use a bit array where the n<sup>th<\/sup> bit is set if n is in the list. That leads to a O(n) solution but there are some problems: <\/p>\n<ul>\n<li>You need a second array to indicate whether a given number is   repeated at least once in the list. <\/li>\n<li>You really need to know the maximum number in the list to size the   bit array properly. <\/li>\n<li>It doesn&#8217;t handle negative numbers gracefully. <\/li>\n<\/ul>\n<p>I did code up a solution like this under the assumption that there were no negative numbers but that doesn&#8217;t solve the problem so we need another solution. <\/p>\n<p> We can use almost the same solution by substituting a hash table for the bit array. With this solution, each integer in the list is a key for the hash table and the value corresponding to the key is the count of the occurrences of the key in the list of integers. We need to go through the list twice<sup><a class=\"footref\" name=\"fnr.1\" href=\"#fn.1\">1<\/a><\/sup>: once to build the hash table and once to check to see if a number in the list has the required number that sums to the target. <\/p>\n<p> The code below implements this solution. The <code>check<\/code> routine on lines 9&ndash;19 does all the real work. For each number in the list (<code>have<\/code>) we calculate the number we need to sum to the target (<code>need<\/code>) and then check to see if <code>need<\/code> is in the hash table. If it is, we&#8217;ve found a solution (line 18), if it&#8217;s not we recursively call <code>check<\/code> with the <code>cdr<\/code> of the list (line 19). Lines 15&ndash;17 check for the special case of a number being exactly half of the target. In that case we&#8217;ve found the solution if the number is in the list at least twice. <\/p>\n<pre class=\"src src-lisp\"><span class=\"linenr\"> 1:  <\/span>(<span style=\"color: #7f007f;\">defun<\/span> <span style=\"color: #0000ff;\">hash-numbers<\/span> (numbers)\r\n<span class=\"linenr\"> 2:  <\/span>  (<span style=\"color: #7f007f;\">let<\/span> ((ht (make-hash-table <span style=\"color: #7a378b;\">:size<\/span> (length numbers))))\r\n<span class=\"linenr\"> 3:  <\/span>    (<span style=\"color: #7f007f;\">dolist<\/span> (n numbers)\r\n<span class=\"linenr\"> 4:  <\/span>      (setf (gethash n ht) (1+ (gethash n ht 0))))\r\n<span class=\"linenr\"> 5:  <\/span>    ht))\r\n<span class=\"linenr\"> 6:  <\/span>\r\n<span class=\"linenr\"> 7:  <\/span>(<span style=\"color: #7f007f;\">defun<\/span> <span style=\"color: #0000ff;\">check-sums<\/span> (goal numbers)\r\n<span class=\"linenr\"> 8:  <\/span>  (<span style=\"color: #7f007f;\">let<\/span> ((ht (hash-numbers numbers)))\r\n<span class=\"linenr\"> 9:  <\/span>    (<span style=\"color: #7f007f;\">labels<\/span> ((check (numbers)\r\n<span class=\"linenr\">10:  <\/span>               (<span style=\"color: #7f007f;\">if<\/span> (null numbers)\r\n<span class=\"linenr\">11:  <\/span>                   nil\r\n<span class=\"linenr\">12:  <\/span>                   (<span style=\"color: #7f007f;\">let*<\/span> ((have (car numbers))\r\n<span class=\"linenr\">13:  <\/span>                          (need (- goal have)))\r\n<span class=\"linenr\">14:  <\/span>                     (<span style=\"color: #7f007f;\">cond<\/span>\r\n<span class=\"linenr\">15:  <\/span>                       ((= need have) (<span style=\"color: #7f007f;\">if<\/span> (&gt; (gethash need ht) 1)\r\n<span class=\"linenr\">16:  <\/span>                                          (list have have)\r\n<span class=\"linenr\">17:  <\/span>                                          (check (cdr numbers))))\r\n<span class=\"linenr\">18:  <\/span>                       ((gethash need ht) (list have need))\r\n<span class=\"linenr\">19:  <\/span>                       (t (check (cdr numbers))))))))\r\n<span class=\"linenr\">20:  <\/span>      (check numbers))))\r\n<span class=\"linenr\">21:  <\/span>\r\n<\/pre>\n<p> This solution won&#8217;t be as fast as the bit array solution (given a decent implementation of bit arrays) but it&#8217;s still pretty efficient and it avoids all the problems with the bit array solution. <\/p>\n<p> Can we do better than O(n)? What if we know the list is sorted? <\/p>\n<p> <b>Update<\/b>: <span class=\"timestamp-wrapper\"> <span class=\"timestamp\">2011-08-05 Fri<\/span><\/span> <br \/> I looked through the solutions that other Programming Praxis  readers submitted looking for something better than O(n). I didn&#8217;t  find anything but <a href=\"http:\/\/programmingpraxis.com\/2011\/07\/19\/sum-of-two-integers\/#comment-3223\">Graham<\/a> and some others noticed that you could  combine the testing with the building of the hash table. Here&#8217;s my  translation of Graham&#8217;s Python solution <\/p>\n<pre class=\"src src-lisp\">(<span style=\"color: #7f007f;\">defun<\/span> <span style=\"color: #0000ff;\">check-sums-2<\/span> (goal numbers)\r\n  (<span style=\"color: #7f007f;\">let<\/span> ((ht (make-hash-table <span style=\"color: #7a378b;\">:size<\/span> (length numbers))))\r\n    (<span style=\"color: #7f007f;\">dolist<\/span> (n numbers)\r\n      (<span style=\"color: #7f007f;\">if<\/span> (gethash (- goal n) ht)\r\n          (<span style=\"color: #7f007f;\">return<\/span> (list n (- goal n)))\r\n          (setf (gethash n ht) t)))))\r\n\r\n<\/pre>\n<p> It still O(n) but faster because it only goes through the list once. It&#8217;s also simpler. <\/p>\n<div id=\"footnotes\">\n<h2 class=\"footnotes\">Footnotes: <\/h2>\n<div id=\"text-footnotes\">\n<p class=\"footnote\"><sup><a class=\"footnum\" name=\"fn.1\" href=\"#fnr.1\">1<\/a><\/sup> Actually, the solution goes through the list 3 times; calculating the size of the list also requires reading through the list. <\/p>\n<\/p><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>A couple of days ago, I wrote about upgrading to Clozure Lisp 1.7 and remarked that I should try it out with a miniproject, perhaps from Programming Praxis. I went over there and found the Sum of Two Integers problem, &hellip; <a href=\"https:\/\/irreal.org\/blog\/?p=189\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[14],"class_list":["post-189","post","type-post","status-publish","format-standard","hentry","category-programming","tag-lisp"],"_links":{"self":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/189","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=189"}],"version-history":[{"count":3,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/189\/revisions"}],"predecessor-version":[{"id":523,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=\/wp\/v2\/posts\/189\/revisions\/523"}],"wp:attachment":[{"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=189"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=189"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/irreal.org\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=189"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}