Product of Array Except Self - C Solution

1. Introduction

This post explores a common problem in array manipulation - calculating the product of all elements in an array except the current element, without using division. This problem is a good example of using prefix and suffix products to achieve an efficient solution. It highlights the importance of thinking creatively about array traversal and accumulation.

Problem

Given an integer array nums, the task is to return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The challenge is to find a solution that runs in O(n) time without using the division operation.

2. Solution Steps

1. Initialize two arrays, left and right, to store the prefix and suffix products.

2. Iterate through nums from left to right, calculating the product of all elements to the left of each element.

3. Iterate through nums from right to left, calculating the product of all elements to the right of each element.

4. For each index i, calculate answer[i] as the product of left[i] and right[i].

5. Return the answer array.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Function to calculate the product of array elements except self
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int* left = (int*)malloc(numsSize * sizeof(int));
    int* right = (int*)malloc(numsSize * sizeof(int));
    int* answer = (int*)malloc(numsSize * sizeof(int));

    left[0] = 1; // Initialize the first element of left
    for (int i = 1; i < numsSize; i++) {
        left[i] = nums[i - 1] * left[i - 1]; // Calculate prefix product
    }

    right[numsSize - 1] = 1; // Initialize the last element of right
    for (int i = numsSize - 2; i >= 0; i--) {
        right[i] = nums[i + 1] * right[i + 1]; // Calculate suffix product
    }

    for (int i = 0; i < numsSize; i++) {
        answer[i] = left[i] * right[i]; // Calculate the product except self
    }

    *returnSize = numsSize;
    free(left);
    free(right);
    return answer;
}

// Main function to test the productExceptSelf function
int main() {
    int nums1[] = {1, 2, 3, 4};
    int numsSize1;
    int* result1 = productExceptSelf(nums1, 4, &numsSize1);
    printf("Product Except Self (Example 1): ");
    for (int i = 0; i < numsSize1; i++) {
        printf("%d ", result1[i]);
    }
    printf("\n");

    int nums2[] = {-1, 1, 0, -3, 3};
    int numsSize2;
    int* result2 = productExceptSelf(nums2, 5, &numsSize2);
    printf("Product Except Self (Example 2): ");
    for (int i = 0; i < numsSize2; i++) {
        printf("%d ", result2[i]);
    }
    printf("\n");

    free(result1);
    free(result2);

    return 0;
}

Output:

Product Except Self (Example 1): 24 12 8 6
Product Except Self (Example 2): 0 0 9 0 0

Explanation:

1. int* left = (int*)malloc(numsSize * sizeof(int)); - Allocate memory for the left prefix product array.

2. left[0] = 1; and for (int i = 1; i < numsSize; i++) - Initialize and compute the prefix products.

3. int* right = (int*)malloc(numsSize * sizeof(int)); - Allocate memory for the right suffix product array.

4. right[numsSize - 1] = 1; and for (int i = numsSize - 2; i >= 0; i--) - Initialize and compute the suffix products.

5. for (int i = 0; i < numsSize; i++) - Iterate to calculate the product of array elements except self.

6. *returnSize = numsSize; - Set the size of the return array.

7. free(left); free(right); - Free allocated memory.

8. The main function tests the productExceptSelf function with two examples and prints the results.