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
- 2 ≤ n ≤ 15
- -10 ≤ a[i] ≤ 10
- Every answer fits in a 64-bit integer.
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
- answer[i] = (product of elements before i) × (product of elements after i).
- 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