## Zillow Interview Question

Software Engineer / DevelopersConstruct two arrays:

C1, C1(1)=1, C1(i) = C1(i-1)*A(i-1)

C1={1, A(1),A(1)*A(2),...,A1*A2*...*A(n-1)} O(N)

C2, C2(N)=1, C2(i)=C2(i+1)*A(i+1)

C2={A2*A3*..*A(N), A3*A4*...*A(N),...,1} O(N)

Now, B(i) = C1(i)*C2(i) O(N)

O(3N) time and O(2N) space

x = a[0] * a[1] * ... * a[n-1] O(n)

b[0] = log inverse (log (x) - log (a[0]))

b[1] = log inverse (log (x) - log (a[1]))

b[n] = log inverse (log (x) - log (a[n]))

Complx will come to O(2n) ~ O(n).

Note:- solution is from my Friend !

log(0) is not defined and log(N) is an expensive operation, but otherwise neat solution.

i think with 3 additional similar size arrays, it might be possible to construct B.

array B1: Walk A, calculate B1[i] = a[i-1] * a[i+1] (should be O(n))

array B2: Walk A calculate B2[i] = B2[i-1] * a[i] (should be O(n))

array B3: Walk A calculate B3[n-i] = B3[n-i+1] * a[i] (should be O(n))

B[i] = B1[i] * B2[i-2] * B3[i+2]

basically, idea would be to exclude the number itself so construct B1 by doing that.

then keep multiplications from [0-(i-2)] and [i+2 to n] in B2 and B3. this shall leave the

item at i behind.

Note:- Solution given by a Friend of mine

if any point of time you have a[i]=0 then whole product will go to zero as a[0]*a[1]*a[2]*..*a[n-1].. no all solution gonna be zero

how about this solution

public static void calcArray(int[] num1){

int[] num2 = new int[num1.length];

int index = 0;

for(int i =0;i<num1.length;i++){

num2[i] =1;

index = 0;

while(index < num1.length){

if(index!=i){

num2[i] *= num1[index];

index++;

}

else

index++;

}

System.out.println(num2[i]);

}

}

1) Loop through all the elements in A and obtain their product

prod=1

for i =0 to n-1 :

prod=prod*A[i]

in the above example it is 24

2) Now loop through B and set it by dividing the product by its corresponding number in A :

B[i]=prod/A[i]

Better approach - no extra space except array B, no division and total time is O(N):

```
void CreateArray(int *a, size_t size, int **b)
{
if (a && size && b)
{
*b = new int[size];
if (*b)
{
// 1. form array B such that b[0] = 1, b[1] = b[0] * a[0], b[2] = a[0] * a[1] = b[1] * a[1], ...
// b[i] = b[i-1] * a[i-1]
(*b)[0] = 1;
for (int i = 1; i < size; i++)
{
(*b)[i] = (*b)[i - 1] * a[i - 1];
}
// 2. set x = 1. b[N-1] = x * b[N-1]; x = x * a[N-1];
// b[N-2] = x * b[N-2] = a[N-1] * b[N-2] = a[N-1] * a[0] * ... * a[N-3]
// b[i] = x * b[i]; x = x * a[i]
int x = 1;
for (int i = size - 1; i >= 0; i--)
{
(*b)[i] = x * (*b)[i];
x = x * a[i];
}
}
}
}
```

```
static int[] multipleExcept(int[] nums) {
if(nums == null || nums.length == 0) return null;
int len = nums.length;
int[] ret = new int[len];
int[] fwd = new int[len];
int[] rev = new int[len];
fwd[0] = nums[0];
rev[len - 1] = nums[len - 1];
for(int i=1; i<len; i++) {
fwd[i] = fwd[i-1] * nums[i];
rev[len - i - 1] = rev[len - i] * nums[len - i - 1];
}
for(int i=0; i<len; i++) {
int n1 = 1;
int n2 = 1;
if(i > 0) n1 = fwd[i-1];
if(i < len - 1) n2 = rev[i+1];
ret[i] = n1 * n2;
}
return ret;
}
```

This solution can be optimized just writing down the concept

- arnab.banerjee.82@gmail.com September 09, 2008say A = { a1,a2,a3,a4}

0 1 2 3 4

prepare B1 = { 1, a1, a1*a2 , a1*a2*a3 , 1 }

prepare B2 = { 1 , a2*a3*a4 , a3*a4 , a4 }

Now, B[1] = a2*a3*a4 = B1[4] * B2[2]

B[2] = a1 * a3*a4 = B1[1] * B2[3]

B[3] = a1*a2 * a4 = B1[2] * B2[4]

B[4] = a1*a2*a3 = B1[3] * B2[1]

hence

B[i] = B1[i-1] * B2[ (i+1) % n]