Ruby - Sum of pairs in an array that add to a certain given input

Question

I'm doing a ruby problem and my solution works. However, it does not work on bigger test cases because it takes too long to process.

The method takes two inputs, an array of numbers and a number.

The goal is to find the first two numbers in the array whose sum is the number provided in the input.

The first pair means that the highest index of the pair is lower than the highest index of any other pairs in the array that add to the number.

Example - ([10, 5, 2, 3, 7, 5], 10)

The answer should be [3, 7] while [5, 5] also sums to 10, the index of the last 5 is 5 and the index of 7 is 4, so [3, 7] comes first.

def sum_pairs(ints, s)
  return nil if ints.empty? || ints.nil?

  x = ints.combination(2).select {|x, y| x + y == s}

  return nil if x.nil? || x.empty?

  ints.rindex(x[0][1]) > ints.rindex(x[-1][1]) ? x.last : x.first 

end

My code worked for all test cases besides those with large arrays.

I was wondering if there was a built in method to help or if I needed to loop through the array differently.

No, and I can see why .rindex would pose a problem in that situation. — hancho
– hancho, Commented Mar 29, 2017 at 3:36
@AustinStehling because sum_pairs([5, 5, 4, 6, 5], 10) returns [4, 6] — Stefan
– Stefan, Commented Mar 29, 2017 at 7:09
@AustinStehling: Please take a look at my answer for a much faster method. — Eric Duminil
– Eric Duminil, Commented Mar 29, 2017 at 7:56

Eric Duminil · Accepted Answer · 2017-03-29 16:22:10Z

10

With a Set, only one pass is needed for this problem :

require 'set'

def sum_pairs(ints, s)
  already_seen = Set.new
  ints.each do |int|
    return [s - int, int] if already_seen.include?(s - int)
    already_seen.add(int)
  end
  nil
end

sum_pairs([10, 5, 2, 3, 7, 5], 10)
# [3, 7]
sum_pairs([10, 5, 2, 3, 7, 5], 20)
# nil

It outputs the result in the correct order and will be much faster than the other solutions.

edited Mar 29, 2017 at 16:22

answered Mar 29, 2017 at 7:51

Eric Duminil

54.6k10 gold badges80 silver badges134 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Ho Man Over a year ago

Yup, this trades off space for a much faster runtime.

Eric Duminil Over a year ago

@HoMan: True. The space needed for the set is smaller than the space already taken by ints. It shouldn't be a problem.

moveson · Accepted Answer · 2017-03-29 06:24:17Z

4

An alternative approach might be to make sure your combinations are always in the correct order of preference, and then use #find instead of #select. The standard Ruby #combination(2) pairs element 0 with all later elements ([10,5],[10,2],[10,3],[10,7],[10,5]) then pairs index 1 with all later elements ([5,2],[5,3],[5,7],[5,5]) and so forth.

You could write a new modified_combination method that pairs element 1 with all earlier elements ([5,10]) then pairs element 2 with all earlier elements ([2,10],[2,5]), then element 3 ([3,10],[3,5],[3,2]) and so forth. This will ensure the pair with the smallest larger index number is always first in the list.

Now you can do:

x = ints.modified_combination.find { |x, y| x, y == s }.reverse

Remember, this will work most efficiently if modified_combination returns an Enumerator rather than an Array (though it will be much more efficient than your original approach in any case).

If you don't want to dig into creating a method that returns an Enumerator, here's a quick-and-dirty solution that achieves the same thing:

def sum_pairs(ints, s)
  (1...ints.size).each do |x|
    (0...x).each do |y|
      return [ints[y], ints[x]] if ints[x] + ints[y] == s
    end
  end
  nil
end

edited Mar 29, 2017 at 6:24

answered Mar 29, 2017 at 5:49

moveson

5,2231 gold badge17 silver badges32 bronze badges

2 Comments

Ho Man Over a year ago

Technically the amortized runtime still takes n^2. Wonder if it's possible to achieve better?

moveson Over a year ago

@HoMan In some cases it might help to do smallest, largest = ints.minmax, then subset = ints.reject { |e| e > (s - smallest) || e < (s - largest) }. Extra time up front for possible savings in the iterations.

Collectives™ on Stack Overflow

Ruby - Sum of pairs in an array that add to a certain given input

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related