Product of Array Except Self

Given an array arr[] of n integers, construct a product array res[] (of the same size) such that res[i] is equal to the product of all the elements of arr[] except arr[i].

Example:

Input: arr[] = [10, 3, 5, 6, 2]
Output: [180, 600, 360, 300, 900]
Explanation:
For i=0, res[i] = 3 * 5 * 6 * 2 is 180.
For i = 1, res[i] = 10 * 5 * 6 * 2 is 600.
For i = 2, res[i] = 10 * 3 * 6 * 2 is 360.
For i = 3, res[i] = 10 * 3 * 5 * 2 is 300.
For i = 4, res[i] = 10 * 3 * 5 * 6 is 900.
Input: arr[] = [12, 0]
Output: [0, 12]
Explanation:
For i = 0, res[i] = 0.
For i = 1, res[i] = 12.

Try it on GfG Practice

Table of Content

[Naive Approach] Using Nested Loops - O(n^2) Time and O(1) Space
[Better approach] Using Prefix and Suffix Array - O(n) Time and O(n) Space
[Efficient Approach] Using Product Array - O(n) Time and O(1) Space

[Naive Approach] Using Nested Loops - O(n^2) Time and O(n) Space

The idea is to compute the product of all elements except the current one by fixing the index and multiplying all other elements in the array. Doing this for every position generates the required result array.

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int>& arr) {
    int n = arr.size();
  
    // Fill result array with 1
    vector<int> res(n, 1);

    for (int i = 0; i < n; i++) {
      
        // Compute product of all elements except arr[i]
        for (int j = 0; j < n; j++) {
            if (i != j) 
                res[i] *= arr[j];
        }
    }

    return res;
}

int main() {
    vector<int> arr = {10, 3, 5, 6, 2};
    vector<int> res = productExceptSelf(arr);
    for (int val : res) 
        cout << val << " ";
    return 0;
}

#include <stdio.h>

void productExceptSelf(int arr[], int n, int res[]) {
  
    // Initialize result array as 1
    for (int i = 0; i < n; i++) {
        res[i] = 1;
    }

    for (int i = 0; i < n; i++) {
      
      	// Compute product of all elements except arr[i]
        for (int j = 0; j < n; j++) {
            if (i != j) {
                res[i] *= arr[j];
            }
        }
    }
}

int main() {
    int arr[] = {10, 3, 5, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int res[n];
    
    productExceptSelf(arr, n, res);
    
    for (int i = 0; i < n; i++) {
        printf("%d ", res[i]);
    }
    
    return 0;
}

Java

import java.util.Arrays;
class GfG {
    
    static int[] productExceptSelf(int[] arr) {
        int n = arr.length;

        // Initialize the result array as 1
        int[] res = new int[n];
        Arrays.fill(res, 1);
        for (int i = 0; i < n; i++) {

            // Compute the product of all except arr[i]
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    res[i] *= arr[j];
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {10, 3, 5, 6, 2};
        int[] res = productExceptSelf(arr);
        for (int val : res) {
            System.out.print(val + " ");
        }
    }
}

Python

def productExceptSelf(arr):
    n = len(arr)

    # Initialize the result list as 1
    res = [1] * n

    for i in range(n):
        
        # Compute the product of all except arr[i]
        for j in range(n):
            if i != j:
                res[i] *= arr[j]

    return res

if __name__ == "__main__":
    arr = [10, 3, 5, 6, 2]
    res = productExceptSelf(arr)
    print(" ".join(map(str, res)))

using System;

class GfG {
    
    static int[] productExceptSelf(int[] arr) {
        int n = arr.Length;
        int[] res = new int[n];
        Array.Fill(res, 1);

        // Compute product of all elements except arr[i]
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    res[i] *= arr[j];
                }
            }
        }

        return res;
    }

    static void Main(string[] args) {
        int[] arr = {10, 3, 5, 6, 2};
        int[] res = productExceptSelf(arr);
        
        foreach (int val in res) {
            Console.Write(val + " ");
        }
    }
}

JavaScript

function productExceptSelf(arr) {
    let n = arr.length;
    let res = new Array(n).fill(1);

    // Compute product of all elements except arr[i]
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i !== j) {
                res[i] *= arr[j];
            }
        }
    }

    return res;
}

// Driver code
let arr = [10, 3, 5, 6, 2];
let res = productExceptSelf(arr);
console.log(res.join(" "));

Output

180 600 360 300 900

[Better approach] Using Prefix and Suffix Array - O(n) Time and O(n) Space

The idea is to precompute the prefix and suffix products and store them in two arrays. Now we can find the product of array except i-th element, by using these precomputed arrays in constant time.
product of array except i-th element = prefProduct[i] * suffProduct[i]
prefProduct[i] stores product of all elements before i-th index in the array.
suffProduct[i] stores product of all elements after i-th index in the array.

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int> &arr) {
    int n = arr.size();
    vector<int> prefProduct(n), suffProduct(n), res(n);

    // Construct the prefProduct array
    prefProduct[0] = 1;
    for (int i = 1; i < n; i++)
        prefProduct[i] = arr[i - 1] * prefProduct[i - 1];

    // Construct the suffProduct array
    suffProduct[n - 1] = 1;
    for (int j = n - 2; j >= 0; j--)
        suffProduct[j] = arr[j + 1] * suffProduct[j + 1];

    // Construct the result array using
    // prefProduct[] and suffProduct[]
    for (int i = 0; i < n; i++)
        res[i] = prefProduct[i] * suffProduct[i];
	
    return res; 
}

int main() {
    vector<int> arr = {10, 3, 5, 6, 2};
    vector<int> res = productExceptSelf(arr);

    for (int val : res)
        cout << val << " ";
}

Java

import java.util.Arrays;

class GfG {
  
    static int[] productExceptSelf(int[] arr) {
        int n = arr.length;
        int[] prefProduct = new int[n];
        int[] suffProduct = new int[n];
        int[] res = new int[n];

        // Construct the prefProduct array
        prefProduct[0] = 1;
        for (int i = 1; i < n; i++)
            prefProduct[i] = arr[i - 1] * prefProduct[i - 1];

        // Construct the suffProduct array
        suffProduct[n - 1] = 1;
        for (int j = n - 2; j >= 0; j--)
            suffProduct[j] = arr[j + 1] * suffProduct[j + 1];

        // Construct the result array using
        // prefProduct[] and suffProduct[]
        for (int i = 0; i < n; i++)
            res[i] = prefProduct[i] * suffProduct[i];

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {10, 3, 5, 6, 2};
        int[] res = productExceptSelf(arr);

        System.out.println(Arrays.toString(res));
    }
}

Python

def productExceptSelf(arr):
    n = len(arr)
    prefProduct = [1] * n
    suffProduct = [1] * n
    res = [0] * n

    # Construct the prefProduct array
    for i in range(1, n):
        prefProduct[i] = arr[i - 1] * prefProduct[i - 1]

    # Construct the suffProduct array
    for j in range(n - 2, -1, -1):
        suffProduct[j] = arr[j + 1] * suffProduct[j + 1]

    # Construct the result array using
    # prefProduct[] and suffProduct[]
    for i in range(n):
        res[i] = prefProduct[i] * suffProduct[i]

    return res

if __name__ == '__main__':
    arr = [10, 3, 5, 6, 2]
    res = productExceptSelf(arr)
    print(res)

using System;

class GFG {

    static int[] productExceptSelf(int[] arr) {
        int n = arr.Length;
        int[] prefProduct = new int[n];
        int[] suffProduct = new int[n];
        int[] res = new int[n];

        // Construct the prefProduct array
        prefProduct[0] = 1;
        for (int i = 1; i < n; i++)
            prefProduct[i] = arr[i - 1] * prefProduct[i - 1];

        // Construct the suffProduct array
        suffProduct[n - 1] = 1;
        for (int j = n - 2; j >= 0; j--)
            suffProduct[j] = arr[j + 1] * suffProduct[j + 1];

        // Construct the result array using
        // prefProduct[] and suffProduct[]
        for (int i = 0; i < n; i++)
            res[i] = prefProduct[i] * suffProduct[i];

        return res;
    }

    static void Main() {
        int[] arr = {10, 3, 5, 6, 2};
        int[] res = productExceptSelf(arr);

        Console.WriteLine(string.Join(" ", res));
    }
}

JavaScript

function productExceptSelf(arr) {
    const n = arr.length;
    const prefProduct = new Array(n).fill(1);
    const suffProduct = new Array(n).fill(1);
    const res = new Array(n);

    // Construct the prefProduct array
    for (let i = 1; i < n; i++) {
        prefProduct[i] = arr[i - 1] * prefProduct[i - 1];
    }

    // Construct the suffProduct array
    for (let j = n - 2; j >= 0; j--) {
        suffProduct[j] = arr[j + 1] * suffProduct[j + 1];
    }

    // Construct the result array using
    // prefProduct[] and suffProduct[]
    for (let i = 0; i < n; i++) {
        res[i] = prefProduct[i] * suffProduct[i];
    }

    return res;
}

// Driver Code
const arr = [10, 3, 5, 6, 2];
const res = productExceptSelf(arr);
console.log(res.join(" "));

Output

180 600 360 300 900

[Efficient Approach] Using Product Array - O(n) Time and O(1) Space

The idea is to handle two special cases of the input array: when it contains zero(s) and when it doesn't. If the array has no zeros, product of array at any index (excluding itself) can be calculated by dividing the total product of all elements by the current element.

However, division by zero is undefined, so if there are zeros in the array, the logic changes.
If there is exactly one zero, the product for that index will be the product of all other non-zero elements, while the elements in rest of the indices will be zero.
If there are more than one zero, the product for all indices will be zero, since multiplying by zero results in zero.

C++

#include <iostream>
#include <vector>
using namespace std;

vector<int> productExceptSelf(vector<int> &arr) {
    int zeros = 0, idx = -1;
    int prod = 1;

    // Count zeros and track the index of the zero
    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] == 0) {
            zeros++;
            idx = i;
        } else {
            prod *= arr[i];
        }
    }

    vector<int> res(arr.size(), 0);

    // If no zeros, calculate the product for all elements
    if (zeros == 0) {
        for (int i = 0; i < arr.size(); i++)
            res[i] = prod / arr[i];
    }
    // If one zero, set product only at the zero's index
    else if (zeros == 1)
        res[idx] = prod;

    return res;
}

int main() {
    vector<int> arr = {10, 3, 5, 6, 2};
    vector<int> res = productExceptSelf(arr);

    for (int val : res)
        cout << val << " ";
}

Java

import java.util.Arrays;

class GfG {
 
    static int[] productExceptSelf(int[] arr) {
        int zeros = 0, idx = -1, prod = 1;
        int n = arr.length;

        // Count zeros and track the index of the zero
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {
                zeros++;
                idx = i;
            } else {
                prod *= arr[i];
            }
        }

        int[] res = new int[n];
        Arrays.fill(res, 0);

        // If no zeros, calculate the product for all elements
        if (zeros == 0) {
            for (int i = 0; i < n; i++) 
                res[i] = prod / arr[i];
        }
        // If one zero, set product only at the zero's index
        else if (zeros == 1)
            res[idx] = prod;

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {10, 3, 5, 6, 2};
        int[] res = productExceptSelf(arr);

        for (int val : res)
            System.out.print(val + " ");
    }
}

Python

def productExceptSelf(arr):
    zeros = 0
    idx = -1
    prod = 1

    # Count zeros and track the index of the zero
    for i in range(len(arr)):
        if arr[i] == 0:
            zeros += 1
            idx = i
        else:
            prod *= arr[i]

    res = [0] * len(arr)

    # If no zeros, calculate the product for all elements
    if zeros == 0:
        for i in range(len(arr)):
            res[i] = prod // arr[i]
    # If one zero, set product only at the zero's index
    elif zeros == 1:
        res[idx] = prod

    return res


if __name__ == "__main__":
    arr = [10, 3, 5, 6, 2]
    res = productExceptSelf(arr)
    print(" ".join(map(str, res)))

using System;

class GfG {
    static int[] productExceptSelf(int[] arr) {
        int zeros = 0, idx = -1, prod = 1;
        int n = arr.Length;

        // Count zeros and track the index of the zero
        for (int i = 0; i < n; i++) {
            if (arr[i] == 0) {
                zeros++;
                idx = i;
            } else {
                prod *= arr[i];
            }
        }

        int[] res = new int[n];
        Array.Fill(res, 0);

        // If no zeros, calculate the product for all elements
        if (zeros == 0) {
            for (int i = 0; i < n; i++) 
                res[i] = prod / arr[i];
        }
        // If one zero, set product only at the zero's index
        else if (zeros == 1)
            res[idx] = prod;

        return res;
    }

    static void Main(string[] args) {
        int[] arr = {10, 3, 5, 6, 2};
        int[] res = productExceptSelf(arr);

        Console.WriteLine(string.Join(" ", res));
    }
}

JavaScript

function productExceptSelf(arr) {
    let zeros = 0, idx = -1, prod = 1;
	
    // Count zeros and track the index of the zero
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === 0) {
            zeros++;
            idx = i;
        } else {
            prod *= arr[i];
        }
    }

    let res = new Array(arr.length).fill(0);

    // If no zeros, calculate the product for all elements
    if (zeros === 0) {
        for (let i = 0; i < arr.length; i++) 
            res[i] = Math.floor(prod / arr[i]);
    }
    // If one zero, set product only at the zero's index
    else if (zeros === 1)
        res[idx] = prod;

    return res;
}

// Driver Code
let arr = [10, 3, 5, 6, 2];
let res = productExceptSelf(arr);
console.log(res.join(" "));

Output

180 600 360 300 900

Other Mathematical Approaches: Please refer A product array puzzle for more approaches that use log and pow to compute the required result without division operator.

Related Problem:

Construct an Array from XOR of all elements of array except element at same index

Product of Array Except Self

[Naive Approach] Using Nested Loops - O(n^2) Time and O(n) Space

[Better approach] Using Prefix and Suffix Array - O(n) Time and O(n) Space

[Efficient Approach] Using Product Array - O(n) Time and O(1) Space

Explore