Generate all other elements' products of an array

 

Given an input array of number {1,2,3,4,5,6}, output number of array {2*3*4*5*6, 1*3*4*5*6,1*2*4*5*6,1*2*3*5*6,1*2*3*4*6,1*2*3*4*5 }. Do not use divide.

 

Solution:

public int[] getAllProductsExceptSelf(int[] num) {
	if(num == null || num.length == 1) return null;
	final int len = num.length;
	int[] result = new int[len];
	int[] leftProducts = new int[len+1];
	int[] rightProducts = new int[len+1];
	leftProducts[0] = 1;
	rightProducts[len] = 1;
	for(int i=1; i<=len; i++) {
		leftProducts[i] = leftProducts[i-1] * num[i-1];
	}
	for(int i=len-1; i>=0; i--) {
		rightProducts[i] = rightProducts[i+1] * num[i];
		result[i] = leftProducts[i] * rightProducts[i+1];
	}
	
	return result;
}

Time Complexity: O(n).