Compute product of array except self
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
## Problem
Given an integer array `nums` of length `n`, return an array `ans` of length `n` where:
- `ans[i] = (nums[0] * nums[1] * ... * nums[i-1] * nums[i+1] * ... * nums[n-1]) mod M`
- Use `M = 1_000_000_007`.
### Requirements
- Do **not** use division.
- Your solution must run in **O(n)** time per test case.
### Input
- An integer `n` (`1 <= n <= 2e5`)
- An array `nums` of `n` integers (`0 <= nums[i] <= 1e9`)
### Output
- An array `ans` of `n` integers.
### Notes
- Handle zeros correctly (e.g., if there are multiple zeros, all outputs are zero).
### Example
`nums = [1, 2, 3, 4]` → `ans = [24, 12, 8, 6]` (then each taken mod `M`).
Quick Answer: This question evaluates understanding of array manipulation, modular arithmetic, and algorithmic optimization by requiring computation of per-element products excluding the current element without division under a large modulus.
Return ans[i] equal to the product of every nums[j] for j != i, modulo 1_000_000_007, without division.
Constraints
- 1 <= len(nums) <= 200000
- 0 <= nums[i] <= 10^9
Examples
Input: ([1, 2, 3, 4],)
Expected Output: [24, 12, 8, 6]
Explanation: Standard example.
Input: ([0, 2, 3],)
Expected Output: [6, 0, 0]
Explanation: Single zero.
Input: ([0, 2, 0],)
Expected Output: [0, 0, 0]
Explanation: Multiple zeros.
Input: ([5],)
Expected Output: [1]
Explanation: The empty product for one element is 1.
Hints
- Store products before each index in a prefix pass, then multiply by suffix products.