Given an integers array A of length n, calculate array B of length n, where B[i] is the product all elements of array A except A[i]. In other words, let p = A[0] × ... × A[n - 1], B[i] = p / A[i]. Do the computation without using the division operator.

Example

A = [1, 2, 3]
B = [6, 3, 2]
public class Solution {
    /**
     * @param A: Given an integers array A
     * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
        long[] forward = new long[A.size()];
        long[] backward = new long[A.size()];
        
        //Products forward:
        //forward[0] = A[0]
        //forward[1] = A[0] * A[1]
        //forward[2] = A[0] * A[1] * A[2]
        
        forward[0] = A.get(0);
        for(int i = 1; i < A.size(); i++)
            forward[i] = A.get(i) * forward[i - 1];
            
        //Products backward:
        //backward[len - 1] = A[len - 1]
        //backward[len - 2] = A[len - 1] * A[len - 2]
        //backward[len - 3] = A[len - 1] * A[len - 2] * A[len - 3]
        
        backward[A.size() - 1] = A.get(A.size() - 1);
        for(int i = A.size() - 2; i >= 0; i--) {
            backward[i] = A.get(i) * backward[i + 1];
        }
        
        ArrayList<Long> res = new ArrayList<Long>();
        for(int i = 0; i < A.size(); i++) {
            if(i == 0 && i == forward.length - 1)
                res.add(1L);
            else if(i == 0)
                res.add(backward[1]);
            else if(i == forward.length - 1)
                res.add(forward[forward.length - 2]);
            else
                res.add(forward[i - 1] * backward[i + 1]);
        }
        
        return res;
    }
}