Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Product of Array Except Self

Medium · Arrays · Asked at Amazon, Microsoft, Meta, Apple, Adobe

For every index i, print the product of all elements except a[i]. Solve it without using division.

Input

First line: n. Second line: n space-separated integers.

Output

n space-separated products.

Constraints

answer[i] = (product of everything to the left of i) × (product of everything to the right of i). Two passes.

Example 1

Input

4
1 2 3 4

Output

24 12 8 6

Example 2

Input

5
-1 1 0 -3 3

Output

0 0 9 0 0

Hints

  1. answer[i] = (product of elements before i) × (product of elements after i).
  2. One pass left-to-right builds the prefix products; a second pass right-to-left multiplies in the suffix products.

Approach

First pass: ans[i] = product of a[0..i-1] (ans[0] = 1). Second pass from the right with a running suffix product: ans[i] *= suffix; suffix *= a[i]. No division is used, so zeros need no special case. Use 64-bit integers.

Complexity: O(n) time · O(1) extra space (besides the output)

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), ans(n, 1);
    for (auto &x : a) cin >> x;
    for (int i = 1; i < n; i++) ans[i] = ans[i - 1] * a[i - 1];
    long long suffix = 1;
    for (int i = n - 1; i >= 0; i--) {
        ans[i] *= suffix;
        suffix *= a[i];
    }
    for (int i = 0; i < n; i++) cout << ans[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1:]
ans = [1] * n
for i in range(1, n):
    ans[i] = ans[i - 1] * a[i - 1]
suffix = 1
for i in range(n - 1, -1, -1):
    ans[i] *= suffix
    suffix *= a[i]
print(*ans)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n], ans = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        ans[0] = 1;
        for (int i = 1; i < n; i++) ans[i] = ans[i - 1] * a[i - 1];
        long suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= suffix;
            suffix *= a[i];
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(ans[i]).append(i + 1 < n ? " " : "");
        System.out.println(sb);
    }
}

Solve Product of Array Except Self online · All practice problems