Product of All Other Array Numbers

Problem:
Given an array of n integers where n>1, return an array of same size an input array where at every index of the output array should contain the product of all elements in the array except the element at the given index.

Example:
arr[] = {10, 4, 1, 6, 2}
prod[] = {48,120,480,80,240}

Solution:


public int[] product_without_self(int[] arr) {
    int[] result = new int[arr.length];
    result[result.length-1] = 1;
 
    for(int i=arr.length-2; i>=0; i--) {
        result[i] = result[i+1] * arr[i+1];
    }
 
    int left = 1;
    for(int i=0; i<arr.length; i++) {
        result[i] *= left;
        left *= arr[i];
    }
 
    return result;
}

Time Complexity: O(n)
Space Complexity: O(n)

2 Thoughts on “Product of All Other Array Numbers

  1. We need to consider the following 3 cases :
    1. If the array contains single zero : Replace the zero with the product of all elements(of course excluding zero) and put zero in remaining places
    2. If the array contains multiple zeroes : Replace all array elements with zeroes
    3. If the array contains only non-zeros elements.

    Generally we forget to handle corner cases.

  2. Praveen Kumar K on January 15, 2017 at 12:54 pm said:

    This problem looks very straight forward in terms of understanding but little tricky while implementing. The solution explained is elegant and covers corner cases also.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation