public class ProductExceptSelf {
// Computes product of array except self.
// nums = input array
// size = number of elements
// returns a new array containing the result
static int[] productExceptSelf(int[] nums, int size) {
int[] answer = new int[size]; // allocate output array
int prefix = 1;
// ---- Prefix products ----
// answer[i] gets the product of all elements before i
for (int i = 0; i < size; i++) {
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
int suffix = 1;
for (int i = size - 1; i >= 0; i--) {
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;
}
public static void main(String[] args) {
int[] arr = {5, 2, 3, 4};
int size = arr.length;
int[] result = productExceptSelf(arr, size);
System.out.print("Result: ");
for (int x : result) {
System.out.print(x + " ");
}
}
}
/*
run:
Result: 24 60 40 30
*/
