Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator and in O(n).
The above method can be optimized to work in space complexity O(1). Thanks to Dileep for suggesting the below solution.
?
void productArray(int arr[], int n)
{
int i, temp = 1;
/* Allocate memory for the product array */
int *prod = (int *)malloc(sizeof(int)*n);
/* Initialize the product array as 1 */
memset(prod,1,n);
/* In this loop, temp variable contains product of
elements on left side excluding arr[i] */
for(i=0; i {
prod[i] = temp;
temp *= arr[i];
}
/* Initialize temp to 1 for product on right side */
temp = 1;
/* In this loop, temp variable contains product of
elements on right side excluding arr[i] */
for(i= n-1; i>=0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i=0; i printf("%d ", prod[i]);
return;
}
Time Complexity: O(n)
Space Complexity: O(n)
Auxiliary Space: O(1)
Optimization :
The above method can be optimized to work in space complexity O(1). Thanks to Dileep for suggesting the below solution.
?
void productArray(int arr[], int n)
{
int i, temp = 1;
/* Allocate memory for the product array */
int *prod = (int *)malloc(sizeof(int)*n);
/* Initialize the product array as 1 */
memset(prod,1,n);
/* In this loop, temp variable contains product of
elements on left side excluding arr[i] */
for(i=0; i
prod[i] = temp;
temp *= arr[i];
}
/* Initialize temp to 1 for product on right side */
temp = 1;
/* In this loop, temp variable contains product of
elements on right side excluding arr[i] */
for(i= n-1; i>=0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i=0; i
return;
}
Time Complexity: O(n)
Space Complexity: O(n)
Auxiliary Space: O(1)
void ArrayMul(int buf[],int res[],size_t len) /*res[] is assumed to be of size len & all members initialized to 1 */
{
size_t i;
int left = 1,
right = 1;
for(i = 0; i<len;i++)
{
res[i] *= left;
res[lenn-i-1] *= right;
left *= buf[i];
right *= buf[len-i-1];
}
}
Example:
ReplyDeletearr[] = {10, 3, 5, 6, 2}
prod[] = {180, 600, 360, 300, 900}
Algorithm:
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[].
1st Approach
Implementation:
#include
#include
/* Function to print product array for a given array
arr[] of size n */
void productArray(int arr[], int n)
{
/* Allocate memory for temporary arrays left[] and right[] */
int *left = (int *)malloc(sizeof(int)*n);
int *right = (int *)malloc(sizeof(int)*n);
/* Allocate memory for the product array */
int *prod = (int *)malloc(sizeof(int)*n);
int i, j;
/* Left most element of left array is always 1 */
left[0] = 1;
/* Rightmost most element of right array is always 1 */
right[n-1] = 1;
/* Construct the left array */
for(i = 1; i < n; i++)
left[i] = arr[i-1]*left[i-1];
/* Construct the right array */
for(j = n-2; j >=0; j--)
right[j] = arr[j+1]*right[j+1];
/* Construct the product array using
left[] and right[] */
for (i=0; i=0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i=0; i<n; i++)
printf("%d ", prod[i]);
return;
}