{{ message }}

Instantly share code, notes, and snippets.

# pjg/exercise.rb

Last active Nov 22, 2018
Array#pairs
 require 'rspec' class Array def pairs(sum) end end # arr = [1,3,4,5,2,6,-1,0,2] # p arr.pairs(4) # => [[1,3],[4,0],[5,-1],[2,2]] # arr = [1,3,1] # p arr.pairs(4) # => [[1,3]] # arr = [1,3,3,3,1] # p arr.pairs(4) # => [[1,3],[3,1]] RSpec.configure do |config| config.filter_run_when_matching :focus end RSpec.describe 'Array#pairs' do it 'handles empty array' do expect([].pairs(4)).to eql [] end it 'finds pair if there are only 2 matching elements' do expect([1, 3].pairs(4)).to match_array [a_collection_containing_exactly(1, 3)] end it 'handles negative numbers' do expect([-1, 5].pairs(4)).to match_array [a_collection_containing_exactly(-1, 5)] end it 'takes into account each element only once' do expect([1, 3, 1].pairs(4)).to match_array [a_collection_containing_exactly(1, 3)] end it 'handles two pairs' do expect([2, 1, 3, 2].pairs(4)).to match_array [ a_collection_containing_exactly(2, 2), a_collection_containing_exactly(1, 3) ] end it 'handles two pairs with more elements' do expect([1, 3, 3, 3, 1].pairs(4)).to match_array [ a_collection_containing_exactly(1, 3), a_collection_containing_exactly(3, 1) ] end it 'handles complex array' do expect([1, 3, 4, 5, 2, 6, -1, 0, 2].pairs(4)).to match_array [ a_collection_containing_exactly(1, 3), a_collection_containing_exactly(4, 0), a_collection_containing_exactly(5, -1), a_collection_containing_exactly(2, 2) ] end end
 class Array # crude solution O(n^3) def pairs(sum) result = [] reserved = [] each.with_index do |el, index| each.with_index do |next_el, next_index| next if next_index <= index next if reserved.include? index next if reserved.include? next_index if el + next_el == sum result << [el, next_el] reserved << index reserved << next_index end end end result end # solution with index O(n^2) def pairs(sum) result = [] reserved = {} each.with_index do |el, index| each.with_index do |next_el, next_index| next if next_index <= index next if reserved[index] next if reserved[next_index] if el + next_el == sum result << [el, next_el] reserved[index] = true reserved[next_index] = true end end end result end # ideal solution O(n) def pairs(sum) result = [] elements = Hash.new(0) each.with_index do |el, index| desired = sum - el if elements[desired] > 0 result << [el, desired] elements[desired] -= 1 else elements[el] += 1 end end result end end

### gotar commented Nov 22, 2018

 ```def pairs(sum) return enum_for(:pairs, sum).to_a unless block_given? counter = Hash.new(0) each do |item| if counter[sum - item].zero? counter[item] += 1 else counter[sum - item] -= 1 yield [sum - item, item] end end end```

### gotar commented Nov 22, 2018

 ```class Array def pairs(sum) each.with_object([[], []]) do |e, (singles, pairs)| if idx = singles.index { |s| ((s + e) ^ sum).zero? } pairs << [e, singles.delete_at(idx)] else singles << e end end.last end end```

### gotar commented Nov 22, 2018

 ^ podrzucone przez Macka Kubiaka