There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i].

Full Question:

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

Simply, it can be solved in O(n²) time, by using double loop. For example,

int[] multiplicationExceptMe() {
int ret[N] = {1,};
for (int i=0; i < N; i++)
 for (int j=0; j < N; j++) {
  if(i != j)
     ret[i] *= A[j]
 }
return ret;
}

But, we have to solve in in O(n). The idea is to do multiply in both side (i.e. from start to end and from end to start) in each loop.

public static void main(String args[]) {
int input[] = {1, 2, 3, 4, 5};
int ret[] = {1,1,1,1,1};
int n = input.length, left=1, right=1;

for(int i=0; i <n; i++) {
ret[i] = ret[i]*left;  
ret[n-1-i] = ret[n-1-i]*right;
//after multiplication, set new left and right value
left *= input[i];
right *= input[n-i-1];
}

for (int i =0; i<n; i++)
System.out.print(ret[i] +"\t");
}

Obviously, it's O(n) time complexity.

Posted in Big O, C, Google Interview Question, Interview Question, Java, MS interview Question, Programming, Time Complexity