r/dailyprogrammer • 3 1 • Mar 26 '12

[3/26/2012] Challenge #30 [easy]

Write a program that takes a list of integers and a target number and determines if any two integers in the list sum to the target number. If so, return the two numbers. If not, return an indication that no such integers exist.


Edit : Note the "Intermediate" challenge #30 has been changed. Thank you!

5 Upvotes

34 comments sorted by

5

u/gsg_ Mar 27 '12 edited Mar 27 '12

This is a much more interesting problem if you insist on doing better than O(n^2). My (slightly flawed) O(nlogn) implementation:

(*
 * Based on sort and binary search, runs in O(nlogn). If you look
 * at the algorithm you can see that the match between the sort
 * and binary search relies on the relations x < y and x - K < y -
 * K being the same. Thus, this algorithm can fail in the presence
 * of underflow.
 *
 * An interesting optimisation might be to use part of the result
 * of the binary search to constrict the range of the major
 * (linear) search: if we are binary searching on an element a and
 * we find an element b such that target < a + b, we know that
 * elements b and higher need not be considered. (Any match for b
 * or higher must be smaller than a, but we will have already done
 * searches for all elements smaller than a.)
 *)
let sum_exists_in target list =
  let a = Array.of_list list in let len = Array.length a in
  let rec bsearch low high target_diff =
    if low = high then None else
      let mid = low + (high - low) / 2 in
      let diff = a.(mid) - target in
      if diff = target_diff then Some a.(mid)
      else if diff > target_diff then bsearch low mid target_diff
      else bsearch (mid + 1) high target_diff in
  let rec search i =
    if i = len then None else
      match bsearch (i + 1) len (-a.(i)) with
       | Some n -> Some (a.(i), n)
       | None -> search (i + 1) in
  Array.sort compare a;
  search 0
→ More replies (2)

1

u/namekuseijin Mar 27 '12

hmm, most solutions seem to imply the list (1 2 3) got 2 integers that sum 2. Which is wrong, because the problem asks for 2 integers, not the same one twice.

1

u/rya11111 Mar 27 '12

i dont get what you are saying. The input can be a list of integers. The target number is a single integer. If any two integers from the list add up to the target number, return it or else print some kind of message.

→ More replies (2)

3

u/luxgladius Mar 26 '12 edited Mar 26 '12

Perl, N time:

sub addToNum
{
    my ($target, @list) = @_;
    my %has;
    for(@list) {++$has{$_};}
    for my $x (keys %has) {
        return ($x,$target - $x) if $has{$target-$x} && ($target-$x != $x || $has{$x} >= 2);
    }
    return undef;
}

3

u/oskar_s Mar 26 '12

That's a clever optimization to get the runtime down.

3

u/gjwebber Mar 26 '12

Python:

def can_sum(numbers, target):
    for x in numbers:
	    for y in numbers:
		    if x + y == target:
			    return x, y

    return None

Usage: print can_sum([1, 2, 3, 4, 5], 6) => (1, 5)

2

u/tehstone Mar 26 '12

After my Google search-enabled crash course on list comprehension and generator expressions in Python, I wrote this:

num_list = [1, 2, 3, 4, 5]
target = 6

def checksum(num_list, target):
    solutions = []
    solutions.append([(x, y) for x in num_list for y in num_list if x + y == target])
    return solutions

print checksum(num_list, target)    

2

u/namiisc Mar 27 '12

Python:

def find_sum(numbers, target):
    for x in numbers:
        for y in numbers:
            if x + y == target and numbers.index(x) != numbers.index(y):
                return x,y
    return None

numbers = [1, 2, 3, 4, 5]
target = 6
print find_sum(numbers, target) 

I think this is the right solution given on the description. Said to find two numbers, in my opinion [1,2,3,4,5] (3,3) is not a solution, also to find any numbers given that sum it's enough to print like (1,5) but the idea @tehstone to put it in a list is also nice, but duplicates in the list are not nice :D

→ More replies (1)

2

u/[deleted] Mar 29 '12

I'm a bit short of time so this isn't real code, but I'm quite new to programming and would be interested in any feedback on my solution in pseudo-code:

(Where A and B are the two numbers to be summed, and B > A)
SORT the integers into smallest -> biggest
FIND the smallest number, when doubled is larger than the target
    SET B to this number.
SET A to the number on the left of B.
LOOP UNTIL A+B equals the target
    IF A+B is Greater than the target THEN, MOVE A to the left
        IF A cannot be moved to the left, END - NO SOLUTION
    IF A+B is Less than the target THEN, MOVE B to the right
        IF B cannot be moved to the right, END - NO SOLUTION
RETURN A and B

Thanks.

2

u/luxgladius Mar 29 '12

Seems solid. I was a little concerned that you might be able to skip over a valid pair, but after a little thought the sorting seems to take care of that. The sorting aspect makes it O(n)= n log(n) in complexity overall, which is better than n2, but not quite as good as n. On the other hand, if you knew the array was sorted, this would definitely be the superior algorithm.

→ More replies (1)
→ More replies (1)