May 1, 2012

Array Multiplication Problem - II

The Problem
Given an array A[n] of n numbers. You have to modify A[n] such that A[i] will be equal to multiplication of all the elements of A[n] except A[i] e.g.
A[0] = A[1] * A[2] * ... * A[n-1] and
A[1] = A[0] * A[2] * ... * A[n-1]
You have to solve the problem without using the division operator and in O(n). You cannot make use of another array

C++ Program
#include <iostream>
#define MAX 5

void print_array(int *arr)
{
  for(int i = 0; i < 5; ++i)
    std::cout << arr[i] << " ";
  std::cout << std::endl;
}

int multiply_array(int *arr, int product_of_elems_before, int idx)
{
  if(idx ==  MAX)
  {
    return 1;
  }

  int product_of_elems_after = multiply_array(arr, product_of_elems_before * arr[idx], idx + 1);
  int current = arr[idx];

  //update array with the product
  arr[idx] = product_of_elems_before * product_of_elems_after;

  return product_of_elems_after * current;
}

int main()
{
  int arr[5] = { 2, 3, 4, 1, 5};
  multiply_array(arr, 1, 0);
  print_array(arr);
}
Java Program
public class ArrayMultiplicationInPlace
{
  public static void main(String args[])
  {
     int[] arr = new int[]{ 3, 2, 1, 5, 4 };
     multiplyArray(arr, 1, 0);
     printArray(arr);
  }

  private static int multiplyArray(int[] arr, int productOfElemsBefore, int idx)
  {
    if(idx == arr.length)
    {
      return 1;
    }

    int productOfElemsAfter = multiplyArray(arr, productOfElemsBefore * arr[idx], idx + 1);
    int current = arr[idx];

    //update the array with the multiplication product
    arr[idx] = productOfElemsBefore * productOfElemsAfter;
  
    return productOfElemsAfter * current;
  }

  private static void printArray(int[] arr)
  {
    for(int i = 0; i < arr.length; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }
}

No comments :

Post a Comment