You have an array of integers, and for each index you want to find the product of every integer except the integer at that index

Question

I was going over some interview questions and came across this one at a website. I have come up with a solution in Ruby, and I wish to know if it is efficient and an acceptable solution. I have been coding for a while now, but never concentrated on complexity of a solution before. Now I am trying to learn to minimize the time and space complexity.

Question: You have an array of integers, and for each index you want to find the product of every integer except the integer at that index.

Example:

arr = [1,2,4,5]
result = [40, 20, 10, 8]

# result = [2*4*5, 1*4*5, 1*2*5, 1*2*4]

With that in mind, I came up with this solution.

Solution:

def find_products(input_array)
    product_array = []
    input_array.length.times do |iteration|
        a = input_array.shift
        product_array << input_array.inject(:*)
        input_array << a
    end
    product_array
end

arr = find_products([1,7,98,4])

From what I understand, I am accessing the array as many times as its length, which is considered to be terrible in terms of efficiency and speed. I am still unsure on what is the complexity of my solution.

Any help in making it more efficient is appreciated and if you can also tell the complexity of my solution and how to calculate that, it will be even better.

Thanks

Answer 1

def product_of_others(arr)
  case arr.count(0)
  when 0
    total = arr.reduce(1,:*)
    arr.map { |n| total/n }
  when 1
    ndx_of_0 = arr.index(0)
    arr.map.with_index do |n,i|
      if i==ndx_of_0
        arr[0,ndx_of_0].reduce(1,:*) * arr[ndx_of_0+1..-1].reduce(1,:*)
      else
        0
      end
    end
  else
    arr.map { 0 }
  end
end

product_of_others [1,2,4,5]  #=> [40, 20, 10, 8]
product_of_others [1,-2,0,5] #=> [0, 0, -10, 0]
product_of_others [0,-2,4,5] #=> [-40, 0, 0, 0] 
product_of_others [1,-2,4,0] #=> [0, 0, 0, -8]
product_of_others [1,0,4,0]  #=> [0, 0, 0, 0]
product_of_others []         #=> []

For the case where arr contains no zeroes I used arr.reduce(1,:*) rather than arr.reduce(:*) in case the array is empty. Similarly, if arr contains one zero, I used .reduce(1,:*) in case the zero was at the beginning or end of the array.