mediumArrays & HashingPure DSA~22 min
Exclusive Metric Product
A metrics service computes, for each sensor, the product of every other sensor's reading — a normalisation step. Division is banned because a single zero reading would blow it up, so compute each exclusive product directly.
Problem
Given an array nums, return an array out where out[i] is the product of all elements except nums[i], computed without using division.
Input
An array nums of length n (2 ≤ n ≤ 10^5); the full product fits in a 64-bit integer.
Output
An array out of length n.
Constraints
- 2 ≤ n ≤ 100,000
- Division is not allowed
- Run in O(n) time
Examples
Example 1
Input
nums = [1, 2, 3, 4]
Output
[24, 12, 8, 6]
out[0]=2·3·4=24, out[1]=1·3·4=12, out[2]=1·2·4=8, out[3]=1·2·3=6.
Example 2
Input
nums = [2, 3]
Output
[3, 2]
Each position holds the other element.