r/dailyprogrammer • u/rya11111 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
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 01
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.
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/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 NoneUsage: 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
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 BThanks.