Sunday, June 6, 2010

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).

Answer:
void mult_of_other_no_div(int* data, int* out, int size)
{
  //O(n)
  int multi = 1;
  int i;

  for(i = 0; i < size; i++)
    {
      out[i] = multi;
      multi *= data[i];
    }

  multi = 1;
  for(i = size-1; i >= 0; i--)
    {
      out[i] *= multi;
      multi  *= data[i];
    }      
}

No comments:

Post a Comment