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)

One Thought 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.

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