/*
Computes product of array except self.
nums = input list
returns a new list containing the result
*/
fun productExceptSelf(nums: List<Int>): List<Int> {
val size = nums.size
val answer = MutableList(size) { 1 }
// ---- Prefix products ----
// answer[i] gets product of all elements before i
var prefix = 1
for (i in 0 until size) {
answer[i] = prefix // store prefix product
prefix *= nums[i] // update prefix
// Example for nums = listOf(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 in size - 1 downTo 0) {
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)
}
return answer
}
fun main() {
val arr = listOf(5, 2, 3, 4)
val result = productExceptSelf(arr)
print("Result: ")
for (x in result) {
print("$x ")
}
}
/*
run:
Result: 24 60 40 30
*/
