CODEWITHSUNDEEP
rubymethods
S H
S H

Reputation: 161

How should I write this method?

The question's prompt is:

Write a method that takes an array of numbers. If a pair of numbers in the array sums to zero, return the positions of those two numbers. If no pair of numbers sums to zero, return nil.

I'm not sure how to approach this problem and what would be the simplest way. Would this involve the .index method?

def two_sum(nums)
end

two_sum([1,3,5,-3])

Upvotes: 0

Views: 226

Answers (4)

bdbasinger
bdbasinger

Reputation: 175

As always, there are usually many ways to solve a problem, especially with Ruby. If you had come from another language like Java or Python, there is a great chance you might not be already familiar with the each_with_index or each.with_index methods. Without over complicating the solution, just break the problem down into two separate while loops, and return the indexes of the pair that equates to zero if it exists. Ruby provides many methods to make life much easier, but without knowing the majority of them, you'll still be able to solve a plethora of problems with a solid foundation of the basics of programming.

def two_sum(nums)
  i = 0
  while i < nums.length
    j = 0
    while j < nums.length
      if nums[i] + nums[j] == 0
        return i, j
      end
      j += 1
    end
    i += 1
  end
  return nil
end`

Upvotes: 0

Cary Swoveland
Cary Swoveland

Reputation: 110755

This returns offsets for all pairs of values that sum to zero. The return value is not unique, however. If, for example, a = [1,1,1,-1,-1], pairs summing to zero might be at offsets [[0,3],[1,4]] or [[1,3],[2,4]] or other values.

Code

def match_zero_sums(arr)
  h = arr.each_with_index.group_by(&:first)
  h.keys.select { |k| k >= 0 }.each_with_object([]) do |k,a|
    while (k==0 && h[k].size > 1) || (k>0 && h[k].any? && h[-k].any?)
      a << [h[k].shift.last, h[-k].shift.last]
    end if h.key?(-k)
  end
end

Example

arr = [2,3,0,0,-2,-3,4,-3,0,3]
match_zero_sums(arr)
  #=> [[0, 4], [1, 5], [9, 7], [2, 3]]

Explanation

For arr in the example:

enum0 = arr.each_with_index
  #=> #<Enumerator: [2, 3, 0, 0, -2, -3, 4, -3, 0, 3]:each_with_index> 
h = enum0.group_by(&:first)
  #=> { 2=>[[2, 0]], 3=>[[3, 1], [3, 9]], 0=>[[0, 2], [0, 3], [0, 8]],
  #    -2=>[[-2, 4]], -3=>[[-3, 5], [-3, 7]], 4=>[[4, 6]]} 
non_neg_keys = h.keys.select { |k| k >= 0 }
  #=> [2, 3, 0, 4]
enum1 = non_neg_keys.each_with_object([])
  #=> #<Enumerator: [2, 3, 0, 4]:each_with_object([])> 
k,a = enum1.next
  #=> [2, []] 
k #=> 2 
a #=> [] 
h.key?(-k)
  #=> h.key?(-2) => true

so execute the while loop:

k==0 && h[k].size > 1
  #=> 2==0 && h[2].size > 1
  #=> false && true => false
k>0 && h[k].any? && h[-k].any?
  #=> 2>0 && h[2].any? && h[-2].any?
  #=> true && true && true => true
false || true #=> true

so compute:

a << [h[k].shift.last, h[-k].shift.last]
  #=> a << [h[2].shift.last, h[-2].shift.last]
  #=> a << [[2,0].last, [-2,4].last]
  #=> a << [0,4]

so now:

a #=> [[0,4]]

and

h #=> { 2=>[], 3=>[[3, 1], [3, 9]], 0=>[[0, 2], [0, 3], [0, 8]],
  #    -2=>[], -3=>[[-3, 5], [-3, 7]], 4=>[[4, 6]]}

The remaining calculations are similar.

Upvotes: 0

Ajedi32
Ajedi32

Reputation: 48438

As with a lot of things in Ruby, there are a couple different ways of doing this. The "classic" approach to this problem would be to use two nested loops:

def two_sum(nums)
  for i1 in 0...nums.length
    for i2 in i1...nums.length
      # Inside this loop, nums[i1] represents one number in the array
      # and nums[i2] represents a different number.
      #
      # If we find that the sum of these numbers is zero...
      if nums[i1] + nums[i2] == 0
        # Then we have our answer
        return i1, i2
      end
    end
  end

  # At this point we've checked every possible combination and haven't
  # found an answer, so a pair of numbers that sum to zero in that array
  # must not exist. Return nil.
  nil
end

The other approach uses Ruby magic to do the same thing in a somewhat more expressive way:

def two_sum(nums)
  result_pair = nums.each_with_index.to_a.combination(2).find{|n1, n2| n1.first + n2.first == 0}
  result_pair && result_pair.map(&:last)
end

The breakdown here is a bit more complex. If you'd like to understand it, I recommend looking at the documentation for these methods on Array and Enumerable.

Upvotes: 2

Mircea
Mircea

Reputation: 10566

Here is another way to do this:

def two_sum(nums)
  seen = {}
  nums.each_with_index do |n, i| 
    return seen[-1*n], i if seen.key?(-1*n)
    seen[n] = i
  end
  nil
end

It's faster that the above (you do it in one pass) so O(n). It does use O(n) additional space compared to the naive approach that checks each element against each element (but that one's O(n^2)

Upvotes: 0

Related Questions