A Developer's Diary

May 1, 2012

Array Multiplication Problem

The Problem

Given an array A[n] of n numbers. You have to compose an array O[N] such that O[i] will be equal to multiplication of all the elements of A[n] except A[i] e.g.
O[0] = A[1] * A[2] * ... * A[n-1] and
O[1] = A[0] * A[2] * ... * A[n-1]
You have to solve the problem without using the division operator and in O(n).
C++ Program
#include <iostream>
#define MAX 5

int main()
{
  int arr[MAX] = { 4, 3, 5, 1, 2 };
  int product;

  int product_of_elems_before[MAX] = {0};
  product = 1;
  for(int i = 0; i < MAX; ++i)
  {
    product_of_elems_before[i] = product;
    product *= arr[i];
  }

  int product_of_elems_after[MAX] = {0};
  product = 1;
  for(int i = MAX - 1; i >= 0; --i)
  {
    product_of_elems_after[i] = product;
    product *= arr[i];
  }

  for(int i = 0; i < MAX; ++i)
  {
    arr[i] = product_of_elems_before[i] * product_of_elems_after[i];
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
}
Java Program
public class ArrayMultiplication
{
  public static void main(String args[])
  {
    int[] arr = new int[]{ 3, 2, 1, 4, 5 };
    int product;
    
    int productOfElemsBefore[] = new int[arr.length];
    product = 1;
    for(int i = 0; i < arr.length; ++i)
    {
      productOfElemsBefore[i] = product;
      product *= arr[i];
    }

    int productOfElemsAfter[] = new int[arr.length];
    product = 1;
    for(int i = arr.length - 1; i >= 0; --i)
    {
      productOfElemsAfter[i] = product;
      product *= arr[i];
    }

    for(int i = 0; i < arr.length; ++i)
    {
      arr[i] = productOfElemsBefore[i] * productOfElemsAfter[i];
      System.out.print(arr[i] + " ");
    }
  }
}

No comments :

Post a Comment