Odtnhj

Today I got a task with given array and 'target' which is a sum of 2 integers within that list. After some time I came out with draft solution but it does not seem to be passing all of the tests. Algorithm seems to be considering integer at [0] twice.

def two_sum(numbers, target)

numbers.combination 2 do |a, b|
 if a + b == target
 return numbers.index(a), numbers.index(b)
 end
 end
end

print two_sum([1, 2, 3], 4) # Expected [0, 2] *OK

print two_sum([1234, 5678, 9012], 14690) # Expected [1, 2] *OK

print two_sum([2, 2, 3], 4) # Expected [0, 1]) but I get [0, 0] 

I have tried to use .map first instead of .combination(2) method but with the exact same result :-/

def two_sum(numbers, target)
 [*0..numbers.size-1].combination(2).find 
end

two_sum([1234, 5678, 9012], 14690)
 #=> [1, 2]
two_sum([1234, 5678, 9012], 14691)
 #=> nil

Here is a more efficient method that may prove useful when the arrays are large.

require 'set'

def two_sum(arr, target)
 if target.even?
 half = target/2
 first = arr.index(half)
 if first
 last = arr.rindex(half)
 return [first, last] unless last.nil? || first == last
 end
 end
 a1, a2 = arr.uniq.partition n
 s = a2.to_set
 n = a1.find 
 n.nil? ? nil : [arr.index(n), arr.index(target-n)]
end

If target is even I first check to see if one-half of it appears at least twice in arr. If so, we are finished (except for determining and returning the associated indices). Even if the method does not terminate after this step it is required this step does not result in an early termination it is required before the next steps are performed.

If target is odd or is even but one-half of it appears less than twice in arr I construct a temporary array that contains unique values in arr and then partition that into two arrays, a1, containing values no greater than target/2 and a2, containing values greater than target/2. It follows that if two numbers sum to target one must be in a1 and the other must be in a2.

To speed calculations I then convert a2 to a set s, and then loop through a1 looking for a value n such that s contains target-n. Let's try it.

arr = 100_000.times.map rand(1_000_000) 

puts "target i1 arr[i1] i2 arr[i2] calc time (secs)"
puts "---------------------------------------------------------"

1000.times do
 t = Time.now
 target = rand(1_000_000)
 i1, i2 = two_sum(arr, target)
 print "#target -> "
 print i1.nil? ? "nil " :
 "#i1 #arr[i1] #i2 #arr[i2]"
 puts " #(Time.now-t).round(4) secs"
end

prints

target i1 arr[i1] i2 arr[i2] calc time (secs)
---------------------------------------------------------
215113 -> 41 90943 11198 124170 0.027
344479 -> 0 78758 63570 265721 0.0237
188352 -> 190 79209 39912 109143 0.0275
 457 -> nil 0.0255
923135 -> 78 84600 43928 838535 0.0207
 59391 -> 2 5779 5454 53612 0.0289
259142 -> 73 58864 29278 200278 0.0284
364486 -> 8049 182243 89704 182243 0.001
895164 -> 13 205843 7705 689321 0.0228
880575 -> 20 440073 6195 440502 0.021

We see that arr does not contain two numbers that sum to 457. Also, notice the very short time in the antepenultimate row. That's because one-helf of target (364486/2 #=> 182243) appears at least twice in arr.