Product Array Puzzle

Given an array, construct a product array where product[i] contains the product of all elements except a[i] with O(n) time complexity without using division operator.

Solution using left and right arrays:

 Left array contains product of all elements to the left of i and right array contains product of elements to the right of the array. Product array is obtained by multiplying left and right arrays.

Code:

import java.util.*;

public class Solution {

    static void findProductArraySum(int[] arr) {
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] prod = new int[n];
        left[0] = 1;
        right[n-1] = 1;
        for(int i=1; i<n; i++){
            left[i] = arr[i-1] * left[i-1];
        }
        for(int i=n-2; i>=0; i--){
            right[i] = arr[i+1] * right[i+1];
        }
        for(int i=0; i<n; i++){
            prod[i] = left[i] * right[i];
            System.out.print(prod[i]+" ");
        }
       
      return;
}

    public static void main(String[] args) {
        int[] a = {10, 3, 5, 6, 2};
        findProductArraySum(a);
       
       
}
}

Solution using product array alone:

In first pass product of all elements to the left is stored. In second pass product of all elements to the right is multiplied with right product.

code:

import java.util.*;

public class Solution {

    static void findProductArraySum(int[] arr) {
        int n = arr.length;
        int[] prod = new int[n];
        int temp = 1;
        for(int i=0; i<n; i++){
            prod[i] = temp;
            temp*=arr[i];
        }
        temp = 1;
        for(int i=n-1; i>=0; i--){
            prod[i] *= temp;
            temp *= arr[i];
        }
        for(int i=0; i<n; i++){
            System.out.print(prod[i]+" ");
        }
       
      return;
}

    public static void main(String[] args) {
        int[] a = {10, 3, 5, 6, 2};
        findProductArraySum(a);
       
       
}
}