Array of products of all other numbers

Given an array A of size N, return another resulting array B of the same size N, where B[i] is the products of all numbers in A except for A[i].
EXAMPLE:
INPUT: A = [1,2,3,4]
OUTPUT: B = [24, 12, 8, 6]

My initial thoughts:
We can first compute the products of everything, in the example, this is 1*2*3*4 = 24. Then for each element in the resulting array, we divide the total products by that element in the original array, that is: 24 = 24/1; 12 = 24/2; 8 = 24/3; 6 = 24/4. We need to be careful with the edge cases: where there are zero(s). We cannot divide by zero. Hence, we modify the algorithm. We first compute the products of non-zeros and count the number of zeros in A. Then for position i in B, if A[i]=0, we check if there are at least 2 zeros, if yes, B[i]=0. If not, B[i] should be equal to the products of non-zeros. If A[i]\ne0, we check if there is at least 1 zero, if yes, B[i]=0. Otherwise, B[i] is the product of non-zeros divided by $A[i]$.

Codes:

public static long[] getArrayOfProducts(int[] original) {
        int zeroCounts = 0;
        long products = 1;
        for(int number : original) {
            if(number == 0)
                zeroCounts++;
            else
                products *= number;
        }
        
        long[] result = new long[original.length];
        for(int i = 0; i < result.length; ++i) {
            if(original[i] == 0) {
                if(zeroCounts > 1)
                    result[i] = 0;
                else
                    result[i] = products;
            } else if(zeroCounts > 0) {
            	result[i] = 0;
            } else {
                result[i] = products / original[i];
            }
        }
        
        return result;
    }

Better Solution:
According to the post here:

public static long[] getArrayOfProducts2(int[] original) {
    	long[] results = new long[original.length];
    	results[0] = 1;
    	for(int i = 1; i < original.length; ++i) {
    		results[i] = results[i-1]*original[i-1];
    	}
    	
    	long temp = 1;
    	for(int i = results.length - 1; i >= 0; --i) {
    		results[i] *= temp;
    		temp *= original[i];
    	}
    	return results;
    }

Notice:
If the product is too large so that we hit integer/long overflow, we need to handle that, probably by introducing additional variables to store temporary products.

Advertisements