<filename>mySol/Category/Array/E50_Product_of_Array_Exclude_Itself/src/com/productofArrayExcludeItself/E50_Product_of_Array_Exclude_Itself.java<gh_stars>1-10
package com.productofArrayExcludeItself;
import java.util.*;

/*
Description
Given an integers array A.

Define B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]B[i]=
A[0]∗...∗A[i−1]∗A[i+1]∗...∗A[n−1], calculate B WITHOUT divide operation.Out put B

Example
Example 1:

Input:

A = [1,2,3]
Output:

[6,3,2]
Explanation:

B[0] = A[1] * A[2] = 6; B[1] = A[0] * A[2] = 3; B[2] = A[0] * A[1] = 2

Example 2:

Input:

A = [2,4,6]
Output:

[24,12,8]
Explanation:

B[0] = A[1] * A[2] = 24; B[1] = A[0] * A[2] = 12; B[2] = A[0] * A[1] = 8
*/

public class E50_Product_of_Array_Exclude_Itself {

	public static void main(String[] args) {
		List<Integer> input = new ArrayList<Integer>();
		input.add(1);
		input.add(2);
		input.add(3);
        List<Long> output = productExcludeItself(input);
        System.out.println("input: " + (input) + "\noutput: " + (output));
	}
	
	/*
    solution:
    分两次循环 第一次记录数组从后往前的累乘结果，fi代表i位之后所有元素的乘积 
    第二次循环，从左往右，跳过 i 左侧累乘，右侧直接乘以fi + 1
    */
	
	/*
     * @param nums: Given an integers array A
     * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]
     */
    public static List<Long> productExcludeItself(List<Integer> nums) {
        int len = nums.size();
        ArrayList<Long> B = new  ArrayList<Long>();
        long[] f = new long[len];

        long tmp = 1;
        long now = 1;
        f[len-1] = nums.get(len-1);
        int i ;
        for ( i = len-2; i >= 0; --i)
        {
            f[i] = nums.get(i);
            f[i] = f[i] * f[i+1];
        }

        for ( i = 0; i < len; ++i) {
			
            now = tmp;
            if(i+1<len)
                B.add( now * f[i+1] );
            else
                B.add( now );
            now = nums.get(i);
            tmp = tmp * now;

        }
        return B;
    }

}
