object ProductExceptSelfApp {
/*
Computes the product of the array except self.
nums = input sequence
returns a new sequence containing the result
*/
def productExceptSelf(nums: Seq[Int]): Seq[Int] = {
val size = nums.length
val answer = Array.fill(size)(1)
// ---- Prefix products ----
// answer(i) gets the product of all elements before i
var prefix = 1
for (i <- 0 until size) {
answer(i) = prefix // store prefix product
prefix *= nums(i) // update prefix
// Example for nums = Seq(5,2,3,4):
// prefix values: 1, 5, 10, 30
}
// ---- Suffix products ----
// Multiply each answer(i) by product of all elements after i
var suffix = 1
for (i <- (0 until size).reverse) {
answer(i) *= suffix // combine prefix * suffix
suffix *= nums(i) // update suffix
// suffix values: 1, 4, 12, 24, 120
// final answer: 24, 60, 40, 30
// 24 (24*1) 60 (12*5) 40 (10*4) 30 (30*1)
}
answer.toSeq
}
def main(args: Array[String]): Unit = {
val arr = Seq(5, 2, 3, 4)
val result = productExceptSelf(arr)
print("Result: ")
result.foreach(x => print(s"$x "))
}
}
/*
run:
Result: 24 60 40 30
*/
