Quick Overview

From a Squarepoint technical screen: count the triplets of distinct positions in an integer array whose three values have an even product, and return the count modulo a given number. It tests efficient counting on large inputs, parity with zero and negative values, and remembering to apply the required modulo.

Count Index Triplets With an Even Product Modulo a Given Number

Company: Squarepoint

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an integer array `nums`, count the triplets of indices `(i, j, k)` with `i < j < k` for which the product `nums[i] * nums[j] * nums[k]` is even. Because the count can be large, the original question required the result modulo a fixed number; here that number is passed in as `mod`, and you return the count modulo `mod`. ### Function Signature ```python def count_even_product_triplets(nums: list[int], mod: int) -> int: ``` ### Rules - A triplet is a choice of three different positions, counted once in the order `i < j < k`. Equal values at different positions form different triplets. - An integer is even when it is divisible by 2. Zero is even, and negative numbers follow the same rule: `-4` is even and `-3` is odd. - If `nums` has fewer than three elements, the answer is `0`. - Return a value in the range `[0, mod - 1]`. ### Constraints - `1 <= len(nums) <= 10^5` - `-10^9 <= nums[i] <= 10^9` - `2 <= mod <= 10^9 + 7` - Before the modulo, the count can reach about `1.7 * 10^14`, which exceeds the 32-bit signed range but stays below `2^53`. A product of three values can reach `10^27`, which exceeds the 64-bit range. ### Examples **Example 1** ```text Input: nums = [1, 2, 3, 4], mod = 1000000007 Output: 4 ``` All four triplets have an even product. **Example 2** ```text Input: nums = [5, 7, 9, 2, 11], mod = 1000000007 Output: 6 ``` Only the triplets that include index 3 (value `2`) have an even product, and there are 6 of them. **Example 3** ```text Input: nums = [2, 4, 6, 8, 10, 1], mod = 9 Output: 2 ``` All 20 triplets have an even product, and 20 modulo 9 is 2.

Overview: From a Squarepoint technical screen: count the triplets of distinct positions in an integer array whose three values have an even product, and return the count modulo a given number. It tests efficient counting on large inputs, parity with zero and negative values, and remembering to apply the required modulo.

Read the full Squarepoint Data Scientist interview experience this question came from

Given an integer array `nums` and an integer `mod`, count the triplets of indices `(i, j, k)` with `i < j < k` for which the product `nums[i] * nums[j] * nums[k]` is even, and return that count modulo `mod`. ### Rules - A triplet is a choice of three different positions, counted once in the order `i < j < k`. Equal values at different positions form different triplets. - An integer is even when it is divisible by 2. Zero is even, and negative numbers follow the same rule: `-4` is even and `-3` is odd. - If `nums` has fewer than three elements, the answer is `0`. - Return the count modulo `mod`, which is a value in the range `[0, mod - 1]`. ### Value ranges Before the modulo, the count can reach about `1.7 * 10^14`, which exceeds `2^31 - 1` (but stays below `2^53`), so intermediate counts need 64-bit integers (`long` in Java, `long long` in C++). The returned value is below `mod <= 10^9 + 7` and fits in a 32-bit `int`. A product of three values can reach `10^27`, which exceeds the 64-bit range. ### Constraints - `1 <= len(nums) <= 10^5` - `-10^9 <= nums[i] <= 10^9` - `2 <= mod <= 10^9 + 7` ### Example 1 ```text Input: nums = [5, 7, 9, 2, 11], mod = 1000000007 Output: 6 ``` Only the triplets that include index 3 (value `2`) have an even product, and there are 6 of them. ### Example 2 ```text Input: nums = [2, 4, 6, 8, 10, 1], mod = 9 Output: 2 ``` All 20 triplets have an even product, and 20 modulo 9 is 2.

Constraints

  • 1 <= len(nums) <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 2 <= mod <= 10^9 + 7
  • Before the modulo, the count can reach about 1.7 * 10^14, which exceeds the 32-bit signed range (2^31 - 1) but stays below 2^53.
  • A product of three values can reach 10^27, which exceeds the 64-bit range.
  • If len(nums) < 3 the answer is 0; the returned value lies in [0, mod - 1].

Examples

Input: ([1, 2, 3, 4], 1000000007)

Expected Output: 4

Explanation: Source example 1: all four triplets contain an even value.

Input: ([5, 7, 9, 2, 11], 1000000007)

Expected Output: 6

Explanation: Source example 2: one even among four odds; 10 triplets minus C(4, 3) = 4 all-odd triplets.

Hints

  1. Only whether each value is even or odd affects whether a product is even. Zero and negative even numbers are even.
  2. Ask when a product of three integers fails to be even.
  3. The count before the modulo can exceed 2^31 - 1, and a product of three values can exceed the 64-bit range, so choose numeric types with care.

Loading coding console...

Show the approach

Approach

A product of integers is even exactly when at least one factor is even, so a triplet fails the condition only when all three of its values are odd. Count the odd values o in one pass, testing x % 2 != 0; that test is correct for negative values in every language, whereas x % 2 == 1 misclassifies negative odds in JavaScript, Java and C++, where -3 % 2 is -1. There are C(n, 3) = n(n-1)(n-2)/6 index triplets in total and C(o, 3) = o(o-1)(o-2)/6 all-odd triplets, so the answer is (C(n, 3) - C(o, 3)) mod mod. Correctness: every triplet is either all-odd (odd product) or contains an even value (even product), and these two groups are disjoint and together cover all C(n, 3) triplets. Equal values at different positions are distinct triplets automatically, because the formulas count positions rather than values. Because C(o, 3) <= C(n, 3), the difference is non-negative, so one final modulo gives a value in [0, mod - 1] in every language; reducing each term separately and subtracting could go negative. The pre-modulo count is at most C(10^5, 3), about 1.67 * 10^14, and the intermediate n(n-1)(n-2) stays below 10^15 < 2^53, so 64-bit integers and JavaScript doubles compute it exactly. No three-value product is ever formed, so its 10^27 magnitude never matters. Edge cases: one or two elements return 0 (guarded explicitly, and both formulas also yield 0 below 3); fewer than three odd values make C(o, 3) = 0; an all-odd array returns 0; an all-even array returns C(n, 3) mod mod; zero and negative even values count as even.

Time complexity:
O(n)
Space complexity:
O(1)