Given an array nums, return an array where each element is the product of every other element — without using division, and in O(1) extra space (the output array doesn't count).
Example
Input: 1 2 3 4
Output: 24 12 8 6
Approach
This is prefix sum's multiplicative cousin. Do two passes: a left-to-right pass fills each position with the product of everything before it (a running "prefix product"), then a right-to-left pass multiplies in the product of everything after it (a running "suffix product"). No division needed, and both passes reuse the output array itself as storage.
Walkthrough
python
1n = len(nums)
2result = [1] * n
3prefix = 1
4for i in range(n):
5 result[i] = prefix
6 prefix *= nums[i]
7suffix = 1
8for i in range(n - 1, -1, -1):
9 result[i] *= suffix
10 suffix *= nums[i]
Step 1 / 5
First pass, left to right: each position gets the product of everything before it. The output array doubles as prefix-product storage.
Input format
Line 1: the array, space-separated
Print the result array, space-separated.
Not solved yet
Ctrl+Enter
Editor
nums = list(map(int, input().split()))
n = len(nums)
result = [1] * n
# TODO: two passes — prefix products left-to-right, then multiply in suffix products right-to-left
prefix = 1for i inrange(n):
result[i] = prefix
prefix *= nums[i]
Input (stdin)
Output
Run your code to see output here.
Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.
Editor
nums = list(map(int, input().split()))
n = len(nums)
result = [1] * n
# TODO: two passes — prefix products left-to-right, then multiply in suffix products right-to-left
prefix = 1for i inrange(n):
result[i] = prefix
prefix *= nums[i]
Input (stdin)
Output
Run your code to see output here.
Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.
