7
\$\begingroup\$

A puzzle I was given:

Description:

Write a method that returns the "pivot" index of a list of integers. We define the pivot index as the index where the sum of the numbers on the left is equal to the sum of the numbers on the right. Given [1, 4, 6, 3, 2], the method should return 2, since the sum of the numbers to the left of index 2 is equal to the sum of numbers to the right of index 2 (1 + 4 = 3 + 2). If no such index exists, it should return -1. If there are multiple pivots, you can return the left-most pivot.
You can write the method in any language.

Make sure that the method:

  • runs successfully
  • handles all edge cases
  • is as efficient as you can make it!

Apparently my solution is not efficient enough:

def pivot(arr)
  results = []
  arr.each_with_index do |n,index|
    last      = arr.size - 1
    sum_left  = arr[0..index].inject(:+)
    sum_right = arr[index..last].inject(:+)
    results << index if sum_left == sum_right
  end
  results.any? ? results.first : -1
end
\$\endgroup\$
  • 1
    \$\begingroup\$ Steven, your code is quite inefficient. For example, you calculate last each time through the loop, even though it doesn't change and you add up all the elements each time through the loop. (You include arr[index] in both the left and right sums, which is OK, but not necessary.) Consider calculating an array t such that t[i] is the sum of all elements with indices between 0 and t, inclusive, for i from 0 to arr.size-1. How can you do that efficiently? That reduces your problem to finding n such that t[n-1] == t[arr.size-1] - t[n], or showing that no such n exists. \$\endgroup\$ – Cary Swoveland Jan 28 '14 at 3:23
  • \$\begingroup\$ Thank you for the prompt review Cary. Boy is my face red on that last variable running through the loop. That was clumsy! I like your solution of summing between indices - very elegant and clever. Cheers! \$\endgroup\$ – Steven Garcia Jan 28 '14 at 3:55
  • 1
    \$\begingroup\$ Steven, if you wish to edit your question to include a revised solution, I suggest you write "Edit: ....", and leave your current solution at the bottom. \$\endgroup\$ – Cary Swoveland Jan 28 '14 at 5:05
  • 1
    \$\begingroup\$ stackoverflow.com/questions/5898104/… \$\endgroup\$ – Nakilon Jan 28 '14 at 17:40
  • \$\begingroup\$ en.wikipedia.org/wiki/Partition_problem \$\endgroup\$ – Nakilon Jan 28 '14 at 17:41
7
\$\begingroup\$

Ruby allows -1 as an index that means last, so you don't have to calculate it at all.

Calculating the whole left_sum every time is repeating work since it is always the previous left_sum + arr[index-1] (except for when index = 0). Similarly the right_sum is always the previous right_sum - arr[index].

You don't have to gather all results, so you can terminate early on finding the leftmost solution, or as soon as sum_left > sum_right (assuming there are no negative numbers in arr?) you know there is no solution, so can return -1.

For example (untested)

def find_pivot(arr)
  sum_left = -arr[-1]
  sum_right = arr.inject(:+)
  arr.each_index do |i|
    sum_left  += arr[i-1]
    sum_right -= arr[i]
    if sum_left == sum_right
      return i
    elsif sum_right < sum_left
      # assuming there are no negative numbers we already know there's no solution
      return -1
    end
  end
  return -1 # in case we somehow reach the end without a solution or early termination
end

Initialising sum_left to -arr[-1] is a trick to save on having to add an if statement to detect and handle the first iteration of the loop differently, since it cancels out the effect of sum_left += arr[0-1] which would make sum_left jump to the value of the last value in the array.

\$\endgroup\$
  • \$\begingroup\$ Nat your example worked perfectly. Thanks for schooling me on the negative index. VERY handy trick! \$\endgroup\$ – Steven Garcia Jan 29 '14 at 2:24
1
\$\begingroup\$

Here's another way:

def pivot(arr)
  n = arr.size
  raise ArgumentError "arr.size = #{arr.size} < 3" if n < 3
  ct = 0
  cum = arr.each_with_object([]) { |e,c| c << (ct += e) }
  tot = cum.last
  (1...n-1).each do |i|
    return i if cum[i-1] == tot - cum[i]
  end
  return -1
end

pivot([1, 4,  6,  3,  2])           #=>  2
pivot([1, 4,  6,  3,  2,  8, 1])    #=>  3
pivot([1, 3,  1, -1,  3, -5, 8, 1]) #=>  4
pivot([1, 4,  6,  3,  1,  8])       #=> -1
pivot([1.0, 4.5,  6.0,  3.0,  2.5]) #=>  2

For arr = [1, 4, 6, 3, 2], cum = [1, 5, 11, 14, 16]. Beginning with i = 1 we attempt to find i, 1 <= i <= n-2, such that cum[i-1] == 16 - cum[i].

If the elements of arr are all non-negative,

return i if cum[i-1] == tot - cum[i]

can be replaced with:

return  i if (d = tot - cum[i] - cum[i-1]) == 0
return -1 if d < 0

In this case, cum is non-decreasing, so if

cum[i-1] > tot - cum[i]

no j > i can be the pivot index.

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

Here another solution with no if's and no sum_right, you could skip the first iteration but then you need to check the length of the array first.

def pivot(arr)
  i, sum_left, total = 0, 0, arr.inject(:+)
  sum_left, i = sum_left+arr[i], i+1 until sum_left >= (total-arr[i])/2
  return ((sum_left == (total-arr[i])/2) and (arr.length > 2)) ? i:-1
end    

puts pivot([1, 4,  6,  3,  2])           #=>  2
puts pivot([1, 4,  6,  3,  2,  8, 1])    #=>  3
puts pivot([1, 3,  1, -1,  3, -5, 8, 1]) #=>  4
puts pivot([1, 4,  6,  3,  1,  8])       #=> -1
puts pivot([1.0, 4.5,  6.0,  3.0,  2.5]) #=>  2
puts pivot([3, 4,  6,  3,  4])           #=>  2
puts pivot([3])                          #=>  -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.