ruby - what is wrong with the following array and

Question

Two-Sum

1. Define a method, two_sum, that accepts an array and a target sum (integer) as arguments.
2. The method should return true if any two integers in the array sum to the target.
3. Otherwise, it should return false. Assume the array will only contain integers.

---

def two_sum(array, target)
    i = 0
    sum = []
    while i < array.max
        i = i + 1
        b = i + i
        sum.push(b)
    end
    sum.include?(target)
end

puts "------Two Sum------"

puts two_sum([1,2,3,4,5,6], 8) == true     #(im getting true)

puts two_sum([1,2,3,4,5,6], 18) == false   #(im getting true)

puts two_sum([1,3,6], 6) == false          #(im getting false)

puts two_sum([1,8,2,1], 0) == false        #(im getting true)

Answer 1

You loop through each element of the array, which is a good start. Inside this loop, you need to try adding together each pair of elements. At the moment, all you're pushing to your sum array is i+i: the index doubled (i.e. every even number from 0 to double the largest element of your array).

You could attempt to sum each pair of elements by having two loops, one inside the other. They'd both iterate through the elements of the array. In your inner loop, you'd attempt to add the current element from the outer loop to the current element from the inner loop. If you get any matches, you can return true and quit immediately; otherwise return false.

Answer 2

The ruby solution looks like:

def two_sum(array, target)
  array.combination(2).any? { |v| v.reduce(:+) == target }
end

Array#combination returns all the combinations of two elements and Enumerable#any? returns true if the block evaluates to true and false otherwise.

Answer 3

This is an attempt to speed the calculations when performance is important, particularly when the array is large and contains many duplicate values.

Code

require 'set'

def two_sum(arr, target)
  return true if target.even? && arr.count(target/2) > 1
  st = Set.new
  arr.uniq.each do |n|
    return true if st.include?(target-n)
    st << n
  end
  false
end

Examples

two_sum [1, 4, -4, 4, 5], 6  #=> true
two_sum [1, 3, -4, 3, 4], 6  #=> true
two_sum [1, 3, -4, 3, 5], 5  #=> false

Explanation

The code for even values of target serves two purposes:

• it short-circuits the calculations when the array contains a value that equals one-half of target, and that value appears at least twice in the array; and
• should the aforementioned code not return true, it permits the removal of duplicate values in arr before the remaining calculations are performed.

For the first example the steps are as follows.

arr = [1, 4, -4, 4, 5]
target = 6

target.even?
  #=> 6.even? => true
arr.count(target/2) > 1
  #=> arr.count(3) > 1
  #=> 1 > 1
  #=> false

so true is not returned.

st = Set.new
  => #<Set: {}>
b = arr.uniq
  #=> [1, 4, -4, 5]

The first element of b is now passed to the block.

n = 1
st.include?(target-n)
  #=> st.include?(6-1) => false as the set is empty
st << n
  #=> #<Set: {1}>

The next steps are as follows.

n = 4
st.include?(target-n)
  #=> st.include?(6-4) => false
st << n
  #=> #<Set: {1, 4}>

n = -4
st.include?(target-n)
  #=> st.include?(6-(-4)) => false
st << n
  #=> #<Set: {1, 4, -4}>

n = 5
st.include?(target-n)
  #=> st.include?(6-5) => true

so true is returned.