Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        //given [1,2,3,4]
        //from left to right: 1, 1*(1), 1*1*(2), 1*1*2*(3)
        //from right to left: 1*2*3*1, 1*2*(4), 1*1*(3*4), 1*(2*3*4)
        
        int n = nums.length; 
        int[] ret = new int[n];
        ret[0] = 1;//trick
        for (int i = 1; i < n; i++) {
            ret[i] = ret[i-1]*nums[i-1];
        }
        int right = 1; 
        for (int i = n-1; i >= 0; i--) {
            ret[i] *= right; 
            right *= nums[i];
        }
        return ret;
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s