CareerCup

Multiply all the elements and create a master product value. Then traverse the array and just divide the master product with the element in the corresponding spot and store it. This is linear time.

We can calculate the array B in the following manner.

1. First iterate thru Array A (from i=1 to n) and for each value of A[i] store the product of A[1] ..A[i-1] elements in B[i].
2. Next iterate thru array A (from i=n to 1) and for each value of A[i] store the product of A[i-1] .. A[n] in B[i].
3. After the steps 1 and 2 we will have the required values in array B

code for the same is as follows:

void foo(const int A[], const int len)
{
	int B[len];
	int prod = 1;
	int i=0;

	for(i=0;i<len;i++)
	{
		B[i] = prod;
		prod *= A[i];
	}
	prod = 1;
	for(i=len-1;i>=0;i--)
	{
		B[i] = prod;
		prod *= A[i];
	}

	for(i=0;i<len;i++)
	{
		printf("%d\t", B[i]);
	}
}

oops there was bug in the code

void foo(const int A[], const int len)
{
   int B[len];
   int prod = 1;
   int i=0;

   for(i=0;i<len;i++)
   {
      B[i] = prod;
      prod *= A[i];
   }
   prod = 1;
   for(i=len-1;i>=0;i--)
   {
      B[i] *= prod;
      prod *= A[i];
   }

   for(i=0;i<len;i++)
   {
      printf("%d\t", B[i]);
   }
}

A small optimization:
If the numbers are too large, product for all of them may overflow. We can keep product of (n-1) first and hen traverse. For each element first divide the product by a[i] and then multiply by a[i-1].
As for zeros are concerned, we can handle them separately.

long * product (int *a, int n)
{
int i, count =0;
long product = 1;

//if empty string..
if(n==0)
return NULL;

//Allocate the memory which is initialized to zero...
int *p = calloc(n, sizeof(int));

//Find the product
for(i=0; i<n; i++)
if(a[i] == 0)
count++; //Count number of zeros
else
product = a[i]*product;

if(count > 1) //Everything is zero.. juz return the p
return p;

for(i=0; i<n; i++)
if ( a[i] == 0)
p[i]=product;
else
p[i]=product/a[i];

return p;

}

Nobody though about the overflow???

So to avoid this condition, one must check if the multiplication would lead to the overflow condition. If it does, one should simply divide the product by the number we have while iterating and hence in the worst case it may lead to O(n2) complexity.

One should also ask that even after division, if there is overflow what should be done.

Working code!!

main()
{

int i,l,r,x[5]={5,3,4,1,2},y[5]; // x is the initial array, y is the final array

int n = 5; // n be the size of the array, here already defined as 5

l = 1; // l is the product of the values of the left side of an index in x
r = 1; // r is the product of the values of the right side of an index in x

for (i=0 ; i<5 ; i++) y[i]=1; // initialising all y values to 1

for (i=0 ; i<5 ; i++)
{
y[i] = y[i]*l ;
y[n-i-1] = y[n-i-1]*r;

l = l*x[i];
r = r*x[n-i-1];

}

for (i=0; i<5; i++) printf("%d\n",y[i]);
getch();
}

void arraymultiple(int *input,int *output,int size)
{
long int result=1;
int i;
for(i=0;i<size;i++)
{
output[i]=result;
result*=input[i];
}
result=1;
for(i=size-1;i>=0;i--)
{
output[i]*=result;
result*=input[i];
}
}