pivotindex.rb

# I first implemented a solution in a naive style to feel out an algorithm.
# While sketching the first solution I realized that a version with much less
# complexity is easily written. The second version avoids exponential run-times
# by doing simple arithmetic on each iteration to avoid the call to
# Enumerable#reduce. I left both versions here so that you might get a feel for
# my thought process.

def pivot_index_v1 integers
  pivot = -1
  return pivot if integers.empty?
  length = integers.size
  (1..length-1).each do |index|
    left = integers.take index
    right = integers.last(length - index - 1)
    if left.reduce(:+) == right.reduce(:+)
      pivot = index
      break
    end
  end
  pivot
end

def pivot_index_v2 integers
  pivot = -1
  return pivot if integers.empty?
  length, total, left_sum = integers.size, integers.reduce(:+), 0
  (1..length-1).each do |index|
    left_sum += integers[index-1]
    right_sum = total - integers[index] - left_sum
    if left_sum == right_sum
      pivot = index
      break
    end
  end
  pivot
end

tests = [
  [[1,4,6,3,2], 2],
  [[2,5,7,9,2,45,1,6], -1],
  [[], -1],
  [[1,0,0,0,0,0,1,0,0], 1],
  [[0,0,0,0,0,0,0,1,1], -1],
  [[0,0,0,0,1,0,1], 5]
]

tests.each do |test|
  given = test.first
  expected = test.last
  if pivot_index_v2(given) != expected
    puts "Failure: got #{pivot_index_v2(given)} for #{given.inspect} instead of #{expected}"
  end
end