1
\$\begingroup\$

Here is the task from a beginner's course:

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.

This model solution does not use idiomatic Ruby, because at that point in the course, we had only learned traditional loops. I'm trying to go back now and understand how to use idiomatic Ruby to accomplish the same tasks.

Model solution:

def two_sum(nums)

idx1 = 0

while idx1 < nums.length

idx2 = idx1 + 1

while idx2 < nums.length

  if nums[idx1] + nums[idx2] == 0

    return [idx1, idx2]

  end


  idx2 += 1

end


idx1 += 1

end


return nil

end

My solution:

def two_sum(nums)

answer = []

nums.each_with_index do |num1, idx1|
    nums.each_with_index {|num2, idx2| answer.push(idx1, idx2) if (num1 + num2) == 0 }  
end

    answer.empty? ? nil : answer[0..1]

end

The call of only the first two items in the answer array seems cheap. There must be a better way. I'm just not sure how to work through the array including the index, but also breaking as soon as the array hits a length of two, or however else one might define it.

\$\endgroup\$
  • \$\begingroup\$ In -1, -2, 2, 1 which pair is first? \$\endgroup\$ – vnp Oct 20 '16 at 3:29
  • \$\begingroup\$ Your question title ("Find the indices of the first pair…") doesn't quite match the task (which appears not to care which pair is returned). \$\endgroup\$ – 200_success Oct 29 '16 at 7:01
1
\$\begingroup\$

The problem can be solved in less than quadratic time. Sort the elements by absolute value, then search for consecutive elements that sum up to zero.

def two_sum(nums)
    temp = nums.map.with_index { |x, i| [x, i] }
    temp.sort_by! { |x| x[0].abs }
    for x in temp.zip(temp.rotate)
        if x[0][0] + x[1][0] == 0
            return [x[0][1], x[1][1]]
        end
    end
    return nil
end
\$\endgroup\$
0
\$\begingroup\$

You can use return also within a loop block to exit the method.

Here is my solution, which populates an Hash, were the keys are the numbers and the values are the indexes. If I found a key, that is the minus value, I finish the loop. Otherwise if the number is a new one, it is added to the Hash.

def zero_sums(ns)
  ns.each_with_index.with_object({}) do |(n,i),o|
    return o[-n], i if o.key?(-n)
    o[n] = i unless o.key?(n)
  end
end
\$\endgroup\$
0
\$\begingroup\$

Naïve approach:

def zero_sums(array)
  array[0...-1].each_with_index do |n, i|
    j = array[(i+1)..-1].index(-n)
    return [i, j + i + 1] if j
  end
end

zero_sums([-1, -2, 2, 1]) # => [0, 3]

It simply loops through the values, and for each value it attempts to find a its "inverse" in the remaining array using #index.

A possibly faster approach could be this:

def zero_sums(array)
  sorted = array.each_with_index.sort_by(&:first)
  sorted[0...-1].each do |n, i|
    other = sorted[(i+1)..-1].bsearch { |m, j| m == -n }
    return [i, other.last] if other
  end
end

zero_sums([-1, -2, 2, 1]) # => [1,2]
  • Make an array of [value, index] tuples
  • Sort it by the values
  • Again loop through, but use #bsearch to more quickly search the remaining array for the needed value, though if there are many repeats of the desired value, this may not find the lowest index

As seen above, given the same input, [-1, -2, 2, 1], for first method return [0, 3] while the second returns [1, 2]. Both are accurate, but, as vnp mentioned in a comment, it's not totally clear which one is "first"

\$\endgroup\$
0
\$\begingroup\$

All answers given here are good, but I would like to show the absolute simplest solution to show the power of Ruby:

x.product(x).detect{|a,b| a + b == 0}

Now product gives the Cartesian product pairing each number of the first list with each number of the second list,

For example:

irb(main):013:0> [1, 2, 3].product(["a", "b", "c"])
=> [[1, "a"], [1, "b"], [1, "c"], [2, "a"], [2, "b"], [2, "c"], [3, "a"], [3, "b"], [3, "c"]]

In our case for example given x = [1, 4, -1, 5, -4] this returns:

irb(main):011:0> x.product(x)
=> [[1, 1], [1, 4], [1, -1], [1, 5], [1, -4], [4, 1], [4, 4], [4, -1], [4, 5],
[4, -4], [-1, 1], [-1, 4], [-1, -1], [-1, 5], [-1, -4], [5, 1], [5, 4], [5, -1],
[5, 5], [5, -4], [-4, 1], [-4, 4], [-4, -1], [-4, 5], [-4, -4]]

That is if we take the Cartesian product of a list with itself we get all of the pairs.

detect returns the first value that satisfies the given predicate, that in this case is that the sum of the two elements be 0.

So:

irb(main):010:0> x.product(x).detect{|a,b| a + b == 0}
=> [1, -1]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.