LeetCode 3524 - Find X Value of Array I

The operation described in the problem may initially look unusual, but it is actually equivalent to choosing a non-empty contiguous subarray. When we remove a prefix and a suffix that do not overlap, the elements left behind form a contiguous segment of the original array.

leetcodemediumarraymathdynamic-programming

LeetCode Problem 3524

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming

Solution

LeetCode 3524 - Find X Value of Array I

Problem Understanding

The operation described in the problem may initially look unusual, but it is actually equivalent to choosing a non-empty contiguous subarray.

When we remove a prefix and a suffix that do not overlap, the elements left behind form a contiguous segment of the original array. Conversely, every non-empty contiguous subarray can be obtained by removing everything before it as the prefix and everything after it as the suffix.

Therefore, the problem can be restated as follows:

Given an array nums and an integer k, consider every non-empty contiguous subarray. Compute the product of the elements in that subarray and take the result modulo k. For every possible remainder x in the range [0, k - 1], count how many subarrays produce remainder x.

The output array result has length k, where:

  • result[0] = number of subarrays whose product modulo k equals 0
  • result[1] = number of subarrays whose product modulo k equals 1
  • ...
  • result[k - 1] = number of subarrays whose product modulo k equals k - 1

The constraints provide an important clue:

  • n = nums.length can be as large as 100000
  • k <= 5

The array is very large, but the modulus is extremely small. This strongly suggests that we should build a dynamic programming solution whose state depends on the remainder modulo k.

Some important edge cases include:

  • k = 1, where every product modulo 1 is always 0.
  • Arrays containing values that are multiples of k, since they immediately force many products to become 0 modulo k.
  • Very large values of nums[i] up to 10^9, which means we should never compute actual subarray products directly because they would overflow. Only nums[i] % k matters.
  • Arrays of length 1, where the answer consists of exactly one counted subarray.

Approaches

Brute Force

The most direct solution is to enumerate every subarray.

For each starting index i, we extend the ending index j from i to n - 1, maintaining the product of the current subarray. We compute the remainder modulo k and increment the corresponding counter.

This approach is correct because it explicitly examines every possible remaining subarray after the prefix/suffix removal operation.

However, there are O(n^2) subarrays. With n = 100000, this is far too slow.

Key Insight

The modulus k is at most 5.

Instead of tracking actual products, we only care about their remainders modulo k.

Let:

dp[r] = number of subarrays ending at the previous position whose product modulo k equals r

When we process a new value num, let:

m = num % k

Every existing subarray ending at the previous position can be extended by num.

If a previous subarray had remainder r, the new remainder becomes:

(r * m) % k

We also create a new length-1 subarray consisting only of num.

Since there are only at most 5 possible remainders, updating all states takes O(k) time per element.

This gives an O(nk) solution, which is effectively linear because k <= 5.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Enumerates all subarrays directly
Optimal O(nk) O(k) Dynamic programming over modulo states

Algorithm Walkthrough

  1. Create an array answer of size k, initialized to zero. This will store the final counts for each remainder.
  2. Create an array dp of size k, where dp[r] stores how many subarrays ending at the previous index have product remainder r.
  3. Process the array from left to right.
  4. For the current element, compute:

m = nums[i] % k 5. Create a fresh array next_dp of size k. 6. Start a new subarray containing only the current element.

Increment:

next_dp[m] += 1 7. Extend every previously tracked subarray.

For every remainder r:

  • The old count is dp[r].
  • Appending the current element changes the remainder to:

(r * m) % k

  • Add that count into the corresponding bucket of next_dp.
  1. After building next_dp, every entry represents subarrays ending at the current position.

Add all counts from next_dp into the global answer array. 9. Replace dp with next_dp. 10. After processing all elements, return answer.

Why it works

At every position, dp[r] exactly represents the number of subarrays ending at that position whose product modulo k equals r. Every such subarray is either:

  • A new single-element subarray, or
  • An extension of a subarray ending at the previous position.

These are the only possibilities, and every subarray is counted exactly once when its ending position is processed. Therefore the accumulated counts in answer equal the number of all subarrays producing each remainder.

Problem Understanding

The problem asks us to count how many ways we can perform a single operation on an array nums such that the remaining array is a contiguous subarray, and then compute the product of that remaining subarray modulo k.

The allowed operation is choosing a prefix and a suffix of the array, possibly empty, such that they do not overlap and the remaining array is non-empty. Removing a prefix [0..l-1] and a suffix [r+1..n-1] leaves exactly the subarray nums[l..r]. This means every valid operation corresponds one-to-one with a non-empty contiguous subarray.

So the task reduces to counting, for every subarray, the remainder of its product modulo k, and aggregating how many subarrays produce each remainder from 0 to k-1.

The input nums is an array of positive integers up to 10^9, with length up to 10^5. The integer k is small, at most 5, which is the key constraint that enables an efficient dynamic programming solution. The output is an array of size k where each index x stores the number of subarrays whose product modulo k equals x.

Important edge cases include arrays containing values divisible by k, which immediately force the product of any subarray containing such an element to be 0 modulo k, and arrays of length 1, where only single-element subarrays exist.

Approaches

The brute-force approach considers every possible subarray, computes its product, and then takes modulo k. This is straightforward: iterate over all i, extend to all j >= i, multiply elements, and compute the remainder. While correct, this becomes infeasible because there are O(n^2) subarrays and each multiplication adds overhead.

The key insight is that we do not need to recompute products from scratch. Instead, we can build subarray products incrementally using dynamic programming. Since we only care about results modulo k, and k <= 5, we can maintain a frequency table of product remainders for subarrays ending at each index. For each new element, we either start a new subarray or extend all previous subarrays ending at the previous index, updating their product modulo k.

This reduces the problem from quadratic subarray enumeration to linear traversal with constant-sized state transitions.

Complexity Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Enumerates all subarrays and recomputes product
Optimal DP O(n · k²) O(k) Maintains DP of product remainders per ending index

Algorithm Walkthrough

We define a dynamic programming state where dp[x] represents the number of subarrays ending at the current index whose product modulo k equals x.

We also maintain a global result array result[x] which accumulates counts across all positions.

Steps

  1. Initialize two arrays of size k, dp and result, filled with zeros. These track subarray counts ending at the current index and total counts respectively.
  2. Iterate through each element num in nums, and compute val = num % k. This reduction is valid because multiplication modulo k depends only on remainders.
  3. For each new element, create a fresh DP array new_dp of size k. This will store updated subarray counts ending at the current index.
  4. Start a new subarray consisting only of the current element. Increment new_dp[val] by 1, since a subarray of length one always contributes directly.
  5. Extend all previous subarrays ending at the previous index. For every remainder p in dp, compute (p * val) % k and add dp[p] to new_dp[(p * val) % k].
  6. Add all values from new_dp into result, since all subarrays ending at the current index are now accounted for globally.
  7. Replace dp with new_dp and continue to the next element.

Why it works

The key invariant is that dp[x] always correctly represents all subarrays ending at the current index with product remainder x. Every subarray is counted exactly once when its right endpoint is processed. Because multiplication modulo k is associative and distributive over subarray extension, extending previous results preserves correctness without recomputation.

Python Solution

from typing import List

class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:
        answer = [0] * k
        dp = [0] * k

        for num in nums:
            m = num % k

            next_dp = [0] * k

            # Start a new subarray with only this element.
            next_dp[m] += 1

            # Extend previous subarrays.
            for remainder in range(k):
                count = dp[remainder]
                if count:
                    new_remainder = (remainder * m) % k
                    next_dp[new_remainder] += count

            # Accumulate into final answer.
            for remainder in range(k):
                answer[remainder] += next_dp[remainder]

            dp = next_dp

        return answer

The implementation follows the dynamic programming formulation directly.

The array dp stores counts for subarrays ending at the previous index. For each new element, we build next_dp.

The line:

next_dp[m] += 1

creates the length-1 subarray consisting only of the current element.

The extension loop transforms every previous remainder into a new remainder after multiplication by m.

After next_dp is complete, all of those subarrays end at the current index, so their counts are added into the global result array. Finally, dp is replaced with next_dp and processing continues.

Because the number of remainder states is at most 5, each iteration performs only a constant amount of work. result = [0] * k dp = [0] * k

    for num in nums:
        val = num % k
        new_dp = [0] * k

        new_dp[val] += 1

        for prev_rem in range(k):
            if dp[prev_rem]:
                new_rem = (prev_rem * val) % k
                new_dp[new_rem] += dp[prev_rem]

        for r in range(k):
            result[r] += new_dp[r]

        dp = new_dp

    return result


### Implementation Explanation

The solution maintains two layers of state. The `dp` array represents subarrays ending at the previous index, while `new_dp` builds subarrays ending at the current index. Each element either starts a new subarray or extends all previous ones.

After computing `new_dp`, it is merged into `result`, ensuring all subarrays are counted exactly once. Finally, `dp` is updated for the next iteration.

## Go Solution

```go
func resultArray(nums []int, k int) []int64 {
	answer := make([]int64, k)
	dp := make([]int64, k)

	for _, num := range nums {
		m := num % k

		nextDP := make([]int64, k)

		// Single-element subarray.
		nextDP[m]++

		// Extend previous subarrays.
		for r := 0; r < k; r++ {
			if dp[r] == 0 {
				continue
			}

			newR := (r * m) % k
			nextDP[newR] += dp[r]
		}

		// Accumulate answer.
		for r := 0; r < k; r++ {
			answer[r] += nextDP[r]
		}

		dp = nextDP
	}

	return answer
}

The Go implementation mirrors the Python solution exactly.

The return type is []int64 because the number of subarrays can reach:

$$\frac{n(n+1)}{2}$$

which is approximately 5 * 10^9 when n = 100000, exceeding 32-bit integer limits.

Worked Examples

Example 1

Input:

nums = [1,2,3,4,5]
k = 3

Modulo values:

[1,2,0,1,2]
Step Current Mod dp After Processing Result
1 1 [0,1,0] [0,1,0]
2 2 [0,0,2] [0,1,2]
3 0 [3,0,0] [3,1,2]
4 1 [3,1,0] [6,2,2]
5 2 [3,0,2] [9,2,4]

Final answer:

[9,2,4]

Example 2

Input:

nums = [1,2,4,8,16,32]
k = 4

Modulo values:

[1,2,0,0,0,0]

Processing produces:

Step dp
1 [0,1,0,0]
2 [0,0,2,0]
3 [3,0,0,0]
4 [4,0,0,0]
5 [5,0,0,0]
6 [6,0,0,0]

Accumulating all counts gives:

[18,1,2,0]

Example 3

Input:

nums = [1,1,2,1,1]
k = 2

Modulo values:

[1,1,0,1,1]
Step dp Result
1 [0,1] [0,1]
2 [0,2] [0,3]
3 [3,0] [3,3]
4 [3,1] [6,4]
5 [3,2] [9,6]

Final answer:

[9,6]

result := make([]int64, k)
dp := make([]int64, k)

for _, num := range nums {
    val := num % k
    newDp := make([]int64, k)

    newDp[val] += 1

    for prev := 0; prev < k; prev++ {
        if dp[prev] != 0 {
            newRem := (prev * val) % k
            newDp[newRem] += dp[prev]
        }
    }

    for i := 0; i < k; i++ {
        result[i] += newDp[i]
    }

    dp = newDp
}

return result

}


### Go-specific Notes

In Go, we use `int64` for safety since counts can grow large with up to `10^5` subarrays. Slices are used instead of fixed arrays for flexibility. The logic mirrors the Python solution exactly, with explicit loops replacing Python’s range iteration.

## Worked Examples

### Example 1: nums = [1,2,3,4,5], k = 3

We track `dp` after each element.

| i | num | dp before | new_dp computation | result update |
| --- | --- | --- | --- | --- |
| 0 | 1 | [0,0,0] | [1,0,0] | [1,0,0] |
| 1 | 2 | [1,0,0] | start [0,1,0], extend [0,2,0] | cumulative updated |
| 2 | 3 | ... | ... | ... |

Each step expands subarrays ending at current index. Every subarray is counted exactly when it ends.

Final result becomes `[9,2,4]`.

### Example 2: nums = [1,2,4,8,16,32], k = 4

Since many numbers are divisible by 4, many subarrays collapse to remainder `0`.

The DP quickly accumulates large counts in `dp[0]`, while only a few subarrays contribute to other remainders.

Final output is `[18,1,2,0]`.

### Example 3: nums = [1,1,2,1,1], k = 2

We only track parity of product.

Every subarray is classified by whether it contains a `2` (even product) or not.

The DP accumulates:

- `dp[1]` for odd products
- `dp[0]` for even products

Final result is `[9,6]`.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(nk) | For each element we process all k remainder states |
| Space | O(k) | Only the current DP state and next DP state are stored |

Since `k <= 5`, the algorithm is effectively linear in the length of the array.

The solution never computes actual subarray products, avoiding overflow concerns and ensuring excellent performance even for the maximum input size.

## Test Cases

```python
from typing import List

s = Solution()

assert s.resultArray([1, 2, 3, 4, 5], 3) == [9, 2, 4]  # Example 1
assert s.resultArray([1, 2, 4, 8, 16, 32], 4) == [18, 1, 2, 0]  # Example 2
assert s.resultArray([1, 1, 2, 1, 1], 2) == [9, 6]  # Example 3

assert s.resultArray([5], 3) == [0, 0, 1]  # Single element

assert s.resultArray([7], 1) == [1]  # k = 1

assert s.resultArray([2, 4, 6], 2) == [6, 0]  # All products even

assert s.resultArray([1, 1, 1], 5) == [0, 3, 0, 0, 0]  # Every product = 1

assert s.resultArray([3, 3, 3], 3) == [6, 0, 0]  # Every product divisible by k

assert s.resultArray([2, 2, 2], 5) == [0, 0, 6, 0, 0]  # Powers remain residue 2,4,3,1 cycle

assert s.resultArray([10**9, 10**9, 10**9], 5) == [6, 0, 0, 0, 0]  # Large values

Test Summary

Test Why
[1,2,3,4,5], k=3 Official example
[1,2,4,8,16,32], k=4 Official example
[1,1,2,1,1], k=2 Official example
Single element Smallest array size
k=1 Every remainder becomes 0
All even numbers with k=2 Products immediately become 0
All ones Product never changes
All multiples of k Every subarray maps to remainder 0
Residue cycle example Validates modulo transitions
Very large values Confirms only modulo values matter

Edge Cases

k Equals 1

When k = 1, every integer modulo 1 equals 0. Therefore every subarray contributes to result[0]. A careless implementation might still try to track multiple states, but this solution naturally handles the case because the DP arrays have size 1 and every transition stays in remainder 0.

Single Element Arrays

When the array contains only one element, there is exactly one valid operation, keeping that element. The algorithm correctly creates the single-element subarray through the line:

next_dp[m] += 1

and returns the corresponding count.

Elements Divisible by k

If nums[i] % k == 0, any subarray product that includes this element becomes remainder 0. Such situations often cause counting mistakes in brute-force optimizations. The DP transition handles them automatically because:

(r * 0) % k = 0

so all affected counts flow into remainder 0.

Very Large Numbers

Values may be as large as 10^9. Computing actual products would quickly overflow standard integer types. The implementation never stores full products. It immediately reduces each value to:

nums[i] % k

and performs all computations using only modulo states, making it both safe and efficient. | Time | O(n · k²) | For each element, we update k states and transition across k previous states | | Space | O(k) | Only two arrays of size k are maintained |

The algorithm is efficient because k is bounded by 5, making the quadratic factor negligible, and the solution effectively linear in n.

Test Cases

assert Solution().resultArray([1,2,3,4,5], 3) == [9,2,4]  # sample case 1
assert Solution().resultArray([1,2,4,8,16,32], 4) == [18,1,2,0]  # sample case 2
assert Solution().resultArray([1,1,2,1,1], 2) == [9,6]  # sample case 3

assert Solution().resultArray([5], 3) == [1,0,0]  # single element
assert Solution().resultArray([2,2,2], 2) == [6,1]  # all even numbers
assert Solution().resultArray([1,3,5,7], 2) == [0,10]  # all odd numbers
assert Solution().resultArray([6,10,15], 5) == [3,0,3,0,3]  # multiple divisible cases
Test Why
single element array validates base case handling
all even numbers stresses zero remainder propagation
all odd numbers tests stable multiplicative parity
mixed divisible values ensures correct handling of zero mod transitions

Edge Cases

One important edge case is when the array contains elements divisible by k. In this situation, any subarray containing such an element will have product 0 mod k. The DP correctly handles this because multiplying by 0 collapses all transitions into remainder 0.

Another edge case is when nums has length 1. Here, only a single subarray exists, and the algorithm correctly counts it as a single contribution to nums[0] % k.

A final edge case is when all elements are 1. In this case, every subarray has product 1, so only result[1] (or result[1 % k]) accumulates all counts. The DP handles this naturally because transitions preserve remainder 1 across all extensions.