Katkat
Back

Compute product of array except self

MicrosoftSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to manipulate array prefixes and suffixes to compute aggregate values efficiently without using the division operator, while handling constraints like modular arithmetic.

Problem Statement

Given an integer array nums of length n and an integer mod, return an array result such that result[i] is equal to the product of all elements in nums except nums[i], modulo mod.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= mod <= 10^9
  • You must solve this in O(n) time complexity and O(1) extra space complexity (excluding the output array).
  • You are not allowed to use the division operator.

Example 1

Input: nums = [1, 2, 3, 4], mod = 1000 Output: [24, 12, 8, 6] Explanation: For index 0, 234 = 24. For index 1, 134 = 12. For index 2, 124 = 8. For index 3, 123 = 6.

Example 2

Input: nums = [5, 2, 0], mod = 100 Output: [0, 0, 10] Explanation: Note that 0s in the array require careful handling to avoid incorrect results or division-by-zero scenarios.

Implementation

def product_except_self(nums: list[int], mod: int) -> list[int]:
    # Implement here

Hints

Hint 1

Consider that the product at index `i` is the product of all elements to the left of `i` multiplied by the product of all elements to the right of `i`.

Hint 2

Try creating two passes over the array: one to store the cumulative product from the left and another to accumulate the product from the right.

Hint 3

Since you need O(1) extra space, can you calculate the prefix products in the output array first, and then multiply by the suffix product on the fly during a second pass?

Follow-up questions

  • How would your approach change if you were allowed to use division, but the array could contain zeros?
  • What would be the impact on your algorithm if the numbers were large enough that the product exceeds the 64-bit integer limit, even before the modulo operation?
  • Can you solve this if you are only allowed one pass through the array, or is that mathematically impossible given the dependencies?