The Interview Question Today#12(7-3-19)

Question:
Given an array of n integers arr[], construct a Product Array such that Product array prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator

Example :

Input:    arr[] = {10, 3, 5, 6, 2}
Output: prod[] = {180, 600, 360, 300, 900}

Approach:
1) Construct a temporary array left[] such that left[i] contains product of all elements on left of arr[i] excluding arr[i].
2) Construct another temporary array right[] such that right[i] contains product of all elements on on right of arr[i] excluding arr[i].
3) To get prod[], multiply left[] and right[].

C program:

#include <stdio.h>

// Function to replace each element of the array with the product  of every other element without //using the division operator
void findProduct(int arr[], int n)
{
int left[n], right[n];
int i,j;

// left[i] stores the product of all elements in the sub-array[0..i-1]
left[0] = 1;
for ( i = 1; i < n; i++)
left[i] = arr[i - 1] * left[i - 1];

// right[i] stores the product of all elements in sub-array[i+1..n-1]
right[n - 1] = 1;
for ( j = n - 2; j >= 0; j--)
right[j] = arr[j + 1] * right[j + 1];

// replace each element with product of its left and right sub-array
for ( i = 0; i < n; i++)
arr[i] = left[i] * right[i];
}

int main(void)
{
int arr[100];
        int n,i;
    printf("Enter the Number of Elements present: ");
    scanf("%d",&n);
    printf("\nEnter the values of Elements");
    for(i=0;i<n;i++)
    {
        printf("\nElements %d:",i+1);
        scanf("%d",&arr[i]);
    }


findProduct(arr, n);
for ( i = 0; i < n; i++)
printf("%d ", arr[i]);

return 0;
}

Output:

Enter the Number of Elements present: 5

Enter the values of Elements

Elements 1:1

Elements 2:2

Elements 3:3

Elements 4:4

Elements 5:5

120 60 40 30 24