#include <stdio.h>
#include <stdlib.h>
/*
Computes product of array except self.
nums = input array
size = number of elements
answer = output array (allocated by caller)
*/
void productExceptSelf(const int *nums, int size, int *answer) {
int prefix = 1;
// ---- Prefix products ----
// answer[i] gets 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)
}
}
int main(void) {
int arr[] = {5, 2, 3, 4};
int size = sizeof(arr) / sizeof(arr[0]);
// Allocate output array
int *result = malloc(size * sizeof(int));
if (!result) {
perror("malloc failed");
return 1;
}
productExceptSelf(arr, size, result);
printf("Result: ");
for (int i = 0; i < size; i++) {
printf("%d ", result[i]);
}
printf("\n");
free(result);
return 0;
}
/*
run:
Result: 24 60 40 30
*/
