Puzzle: Vector Multiplication

11 Oct 2011 | By Mihai Roman | Tags google puzzle algorithms
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).
// input: a
// output: b
void multi(int* a, int* b, int n) {
  b[0] = 1;
  for (int i = 1; i < n; i++) {
    b[i] = b[i - 1] * a[i - 1];
  }
  int x = 1;
  for (int i = n - 2; i >= 0; i--) {
    x = x * a[i + 1];
    b[i] *= x;
  }
}

blog comments powered by Disqus