We are given an array containing n numbers. There is no restriction on what the individual number could be. We want to transform this array so that element at any index is replaced by cumulative multiplication of all elements of the array except the one at that index. For example if the array is
A = [5, 6, 7, 8] then after processing it should become A = [6*7*8, 5*7*8, 5*6*8, 5*6*7].
Develop an algorithm to accomplish the above transformation such that the time complexity of the algorithm is O(n) where n is the number of elements in the array.
A = [5, 6, 7, 8] then after processing it should become A = [6*7*8, 5*7*8, 5*6*8, 5*6*7].
Develop an algorithm to accomplish the above transformation such that the time complexity of the algorithm is O(n) where n is the number of elements in the array.
8 comments:
Take two arrays in the first array put
5, 5*6, 5*6*7, 5*6*7*8
in the second array put this.
5*6*7*8, 6*7*8, 7*8, 8
and then array[i] =
(first[i] * second[i])/(array[i]*array[i])
Perfect Solution !!!
The solution wouldnt work if there is a zero is the set
Great Catch, either the number should not have 0 or we have to modify the algorithm given in the comments above
An easier solution would be to just parse through all the numbers and find the total multiplier.
Pass1: Get the value for 5*6*7*8
Pass2: Then array[i] = multiplier / array[i];
You are correct. This is also a possible solution and is better than the previous one as it doesn't require any additional space.
here is inteligient solution..what happens if u are not allowd to do division..then got for it..
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=0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}
/* print the constructed prod array */
for (i=0; i<n; i++)
printf("%d ", prod[i]);
return;
}
Let me Know If Any Flaw in this program
@Shashank The question requires you get the product of the all the elements except the ith element. Your program generates the product of all the elements to the left but not on the right.
Post a Comment