// Computes product of array except self.
// nums = input vector
// returns a new vector containing the result
fn product_except_self(nums: &Vec<i32>) -> Vec<i32> {
let size = nums.len();
let mut answer = vec![1; size];
// ---- Prefix products ----
// answer[i] gets the product of all elements before i
let mut prefix = 1;
for i in 0..size {
answer[i] = prefix; // store prefix product
prefix *= nums[i]; // update prefix
// Example for nums = [5,2,3,4]:
// prefix values: 1, 5, 10, 30
}
// ---- Suffix products ----
// Multiply each answer[i] by product of all elements after i
let mut suffix = 1;
for i in (0..size).rev() {
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
}
fn main() {
let arr = vec![5, 2, 3, 4];
let result = product_except_self(&arr);
print!("Result: ");
for x in result {
print!("{} ", x);
}
}
/*
run:
Result: 24 60 40 30
*/
