This problem was asked by Uber.

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can’t use division?

Solution

I wrote the solutions in Swift. Feel free to comment with your solution in the language of your choice.

Solution 1: The simplest solution is to make a double loop, that multiplies each integer at index i, and then stores the product in the new array at index ii. The product can then be divided by the integer at index i.

let arrayOfInts = [1, 2, 3, 4, 5]
var newArray = Array(repeating: 1, count: arrayOfInts.count)

for i in arrayOfInts.indices {
  for ii in newArray.indices {
    newArray[ii] *= arrayOfInts[i]
  }
  newArray[i] /= arrayOfInts[i]
}

Solution 2: The follow-up challenge is to not use division. This can be accomplished by using a condition that checks if the number being multiplied is at index i; and if so, we just return the value of the current product and continue through the loop.

newArray = Array(repeating: 1, count: arrayOfInts.count)

for i in arrayOfInts.indices {
  for ii in newArray.indices {
    newArray[ii] = i != ii ? newArray[ii] * arrayOfInts[i] : newArray[ii]
  }
}

Solution 3: We can do much better than quadratic time!

func productOfAllNumbersButOne(in array: [Int]) -> [Int] {
  var product = 1
  var arrayOfProducts = Array(repeating: 0, count: array.count)
  for number in array {
    product *= number
  }
  for index in arrayOfProducts.indices {
    arrayOfProducts[index] = product / array[index]
  }
  return arrayOfProducts
}

This problem was provided by Daily Coding Problem. Get exceptionally good at coding interviews by solving one problem every day.

Leave a Reply

Come See Me

San Francisco, CA
hello@ingax.com

See My Work