Pramp – Array of Array Products

Question

Given an array of integers arr, you’re asked to calculate for each index i the product of all integers except the integer at that index (i.e. except arr[i]). Implement a function arrayOfArrayProducts that takes an array of integers and returns an array of the products.

Solve without using division and analyze your solution’s time and space complexities.

Example

1.
input: arr = [8, 10, 2] 
output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10] 

2.
input: arr = [2, 7, 3, 4] 
output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3]

Constraints

• [time limit] 5000ms
• [input] integer arr
  • 0 ≤ arr.length ≤ 20
• [output] array.integer

Solutions

最大困難點是「不能使用除法」

解法：output[i] = arr[1:i].prod() * 1 * arr[i + 1:].prod()

Time Complexity: O(n)
Space Complexity: O(1)

def array_of_array_products(arr):
  # edge case
  if len(arr) < 2:
    return []
  
  arr_product = [1] * len(arr)
  
  product = 1
  for i in range(len(arr)):
    arr_product[i] *= product
    product *=arr[i]
  
  product = 1
  for i in range(len(arr) - 1, -1, -1):
    arr_product[i] *= product
    product *=arr[i]
  
  return arr_product

input = [2, 7, 3, 4] #[8, 10, 2]
print(array_of_array_products(input))

Corner Case

當len(arr)為 1 或 0 時，回傳[]

Last Updated on 2023/08/16 by A1go