CareerCup

This is for the case when we can't use division operation. Maintain two arrays such that:

A[i] contains product of all elements in the input array from 0 to i - 1.

B[i] contains product of all elments from i + 1 to n.

The answer would be:

for(i to n)
  print A[i] * B[i]

The second question of computing A' from A can be done in 0(n).
void find_A_Dash(int arr[MAX])
{
int product = 1,i;
int Num_of_zero = 0;
for(i=0;i<MAX;i++)
{
if(arr[i] == 0)
Num_of_zero ++;
else
product = product * arr[i];
if(Num_of_zero > 1)
break;
}
for(i=0;i<MAX;i++)
{
if(Num_of_zero >1)
{
arr[i] = 0;
continue;
}
arr[i] = (arr[i] == 0)? product: (Num_of_zero == 1)?0:product / arr[i] ;
}
}

How long were each round? Was this in the Seattle office?

2)

void MakeMagic(int src[], int dst[], int N)
{
   if (!N) return;

   int * p = new int [N];

   int index = N-1;
   p[index] = 1;
   p[index-1] = src[index];

   for (--index; index > 0; --index)
      p[index-1] = src[index] * p[index];

   int q = 1;

   for (index = 0; index < N; q *= src[index++])
      dst[index] = q * p[index];

   delete [] p;
}

Hi, I think if we cannot divide we can replace it with substraction. I.e. let P=a1*..*aN. Then ln(P)=ln(a1)+...+ln(aN). Thus we first go through an array and calculate common product. Then a[i] = exp(ln(P)-ln(a[i])). That's all folks.

1. Take product,P, of all the elements of A
for(int i = 0; i < A.length(); i++)
{
A'[i] = P/A[i];
}

void no_division(int *ia, int n)
{
	if(n <= 1)
		return;

	int *A = new int[n];
	int *B = new int[n];

	for(int i = 1; i < n; ++i)
	{
		if(i == 1)
			A[i] = ia[0];
		else
			A[i] = A[i-1]*ia[i-1];
	}

	A[0] = B[n-1] = 1;

	for(int i = n-2; i > -1; --i)
	{
		if(i == n-2)
			B[i] = ia[n-1];
		else
			B[i] = B[i+1]*ia[i+1];
	}

	for(int i = 0; i < n; ++i)
		ia[i] = A[i]*B[i];

	delete[] B;
	delete[] A;
}

static void productOfRest(int[] a)
{
int[] b = new int[a.length];

int prod = 1;
for (int i = 0; i < b.length; i++) {
b[i] = prod;
prod *= a[i];
}
prod = 1;
for (int i = b.length; i--> 0;) {
b[i] *= prod;
prod *= a[i];
}
}

<pre lang="java" line="1" title="CodeMonkey50563" class="run-this">import java.util.*;
import java.lang.*;

class Main
{
public static void main (String[] args) throws java.lang.Exception
{
System.out.print("Hello World");
}
}
</pre><pre title="CodeMonkey50563" input="yes">static void productOfRest(int[] a)
{
int[] b = new int[a.length];

int prod = 1;
for (int i = 0; i < b.length; i++) {
b[i] = prod;
prod *= a[i];
}
prod = 1;
for (int i = b.length; i--> 0;) {
b[i] *= prod;
prod *= a[i];
}
}</pre>

the simplest solution is to start at the end of the array and multiply as you make your way to the beginning.

int k = 1;
for(int i = length(A) -1,i>0,i--){
 A'[i]=A[i]*k
k=A'[i]}

the solution where we keep 2 arrays [0..pos-1],[pos+1..n] and multiply them is same as
for i in 0..n
if (i != pos) prod*=A[i]
So, i don't see any benefit..
the optimization may be that we can maintain a product FOR ONCE, and divide it as and when we get a A[pos] to get the answer. BUT given that divide is not acceptable Aleks' answer seems good. we can maintain sum of logs FOR ONCE and subtract from it any log(A[pos]), given pos. (if calculating logs is costly .. cache them as well using a hashmap)..
exp of result sum should give the answer..

the solution where we keep 2 arrays [0..pos-1],[pos+1..n] and multiply them is same as
for i in 0..n
if (i != pos) prod*=A[i]
So, i don't see any benefit..
the optimization may be that we can maintain a product FOR ONCE, and divide it as and when we get a A[pos] to get the answer. BUT given that divide is not acceptable Aleks' answer seems good. we can maintain sum of logs FOR ONCE and subtract from it any log(A[pos]), given pos. (if calculating logs is costly .. cache them as well using a hashmap)..
exp of result sum should give the answer..

the solution where we keep 2 arrays [0..pos-1],[pos+1..n] and multiply them is same as

for i in 0..n 
    if (i != pos) prod*=A[i]

So, i don't see any benefit..
the optimization may be that we can maintain a product FOR ONCE, and divide it as and when we get a A[pos] to get the answer. BUT given that divide is not acceptable Aleks' answer seems good. we can maintain sum of logs FOR ONCE and subtract from it any log(A[pos]), given pos. (if calculating logs is costly .. cache them as well using a hashmap)..
exp of result sum should give the answer..

the solution where we keep 2 arrays [0..pos-1],[pos+1..n] and multiply them is same as

for i in 0..n 
    if (i != pos) prod*=A[i]

So, i don't see any benefit..
the optimization may be that we can maintain a product FOR ONCE, and divide it as and when we get a A[pos] to get the answer. BUT given that divide is not acceptable Aleks' answer seems good. we can maintain sum of logs FOR ONCE and subtract from it any log(A[pos]), given pos. (if calculating logs is costly .. cache them as well using a hashmap)..
exp of result sum should give the answer..