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.