CODEWITHSUNDEEP
arraysruby
hancho
hancho

Reputation: 1437

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

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.

Upvotes: 2

Views: 3190

Answers (2)

Eric Duminil
Eric Duminil

Reputation: 54223

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.

Upvotes: 10

moveson
moveson

Reputation: 5213

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

Upvotes: 4

Related Questions