LeetCode 3524: Find X Value of Array I

Problem Overview

LeetCode 3524, Find X Value of Array I, asks us to count the number of non-empty contiguous subarrays whose product has each possible remainder when divided by k.

You are given:

• An array of positive integers nums
• A positive integer k

You can perform one operation by removing a prefix and a suffix from nums, while keeping at least one element.

The goal is to return an array result of size k, where:

• result[0] = number of valid remaining subarrays whose product % k == 0
• result[1] = number of valid remaining subarrays whose product % k == 1
• ...
• result[k - 1] = number of valid remaining subarrays whose product % k == k - 1

Understanding the Operation

At first, the operation may look more complicated than it really is.

We are allowed to remove:

• Any prefix from the beginning
• Any suffix from the end

The remaining elements must be non-empty.

For example:

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

If we remove:

[1]

from the prefix and:

[5]

from the suffix, the remaining array is:

[2, 3, 4]

The remaining elements are always contiguous.

Therefore:

Choosing a prefix and suffix is equivalent to choosing one non-empty contiguous subarray.

So instead of thinking about removing prefixes and suffixes, we can think about all possible non-empty contiguous subarrays.

What Do We Need to Calculate?

For every non-empty contiguous subarray:

1. Calculate the product of its elements.
2. Calculate the product modulo k.
3. Count how many subarrays produce each remainder.

For example:

nums = [1, 2, 3]

The non-empty subarrays are:

[1] [2] [3] [1, 2] [2, 3] [1, 2, 3]

If k = 3, their product remainders are:

[1] -> 1 % 3 = 1

[2] -> 2 % 3 = 2

[3] -> 3 % 3 = 0

[1, 2] -> 2 % 3 = 2

[2, 3] -> 6 % 3 = 0

[1, 2, 3] -> 6 % 3 = 0

Therefore:

result = [3, 1, 2]

This means:

• 3 subarrays have product remainder 0
• 1 subarray has product remainder 1
• 2 subarrays have product remainder 2

Why Can’t We Check Every Subarray Directly?

An array of length n contains:

n * (n + 1) / 2

non-empty subarrays.

For:

n = 100000

there can be approximately:

5,000,050,000

subarrays.

Therefore, generating every subarray and calculating its product individually would be too slow.

We need a more efficient approach.

Key Observation

The most important constraint is:

1 <= k <= 5

This means there are at most 5 possible remainders:

0, 1, 2, ..., k - 1

We do not need to store the actual product of every subarray.

We only need to know:

What is the product remainder modulo k?

This allows us to use dynamic programming based on the product remainder.

Dynamic Programming Approach

We maintain an array called dp.

Meaning of dp

dp[r] represents:

The number of contiguous subarrays ending at the previous index whose product has remainder r when divided by k.

For example, if:

dp[2] = 5

it means there are 5 subarrays ending at the previous position whose product satisfies:

product % k = 2

We do not need to store those 5 subarrays individually.

We only store their count.

Processing a New Number

Suppose the current number is:

num

When we process it, there are two possibilities.

1. Start a New Subarray

The current number can form a subarray by itself:

[num]

Its remainder is:

num % k

So we perform:

next[num % k]++

2. Extend Previous Subarrays

Suppose an existing subarray has product remainder:

r

When we append num, its new product remainder becomes:

(r * (num % k)) % k

Therefore:

newRemainder = (r * value) % k

where:

value = num % k

If there are dp[r] subarrays with remainder r, all of them produce the same new remainder when num is appended.

So we perform:

next[newRemainder] += dp[r]

Why Do We Use next Instead of Updating dp Directly?

We use two arrays:

• dp = subarrays ending at the previous position
• next = subarrays ending at the current position

For every new number, we calculate all states in next.

After processing the number:

dp = next

This prevents newly created states from being reused again during the same iteration.

Step-by-Step Example

Consider:

nums = [1, 2, 3]

k = 3

Initially:

dp = [0, 0, 0]

result = [0, 0, 0]

Process num = 1

First:

value = 1 % 3 = 1

Start a new subarray:

[1]

Its remainder is 1.

So:

next = [0, 1, 0]

Add it to the answer:

result = [0, 1, 0]

Then:

dp = [0, 1, 0]

This represents:

[1] -> remainder 1

Process num = 2

Calculate:

value = 2 % 3 = 2

Start a New Subarray

[2]

Its remainder is:

2 % 3 = 2

So:

next = [0, 0, 1]

Extend Previous Subarrays

Previous:

dp = [0, 1, 0]

There is one subarray with remainder 1:

[1]

Append 2:

[1, 2]

Its product is:

1 * 2 = 2

Therefore:

2 % 3 = 2

So:

next[2] += dp[1]

Now:

next = [0, 0, 2]

The two subarrays ending at index 1 are:

[2] [1, 2]

Both have remainder 2.

Update the global answer:

result = [0, 1, 2]

Then:

dp = [0, 0, 2]

Process num = 3

Calculate:

value = 3 % 3 = 0

Start a New Subarray

[3]

Its remainder is:

3 % 3 = 0

So:

next = [1, 0, 0]

Extend Previous Subarrays

Previous:

dp = [0, 0, 2]

There are 2 subarrays with remainder 2:

[2] [1, 2]

Append 3 to both.

For both:

2 * 3 % 3 = 0

Therefore:

next[0] += 2

Now:

next = [3, 0, 0]

These 3 subarrays are:

[3] [2, 3] [1, 2, 3]

All have product remainder 0.

Add them to the answer:

result = [3, 1, 2]

Why Does This Count Every Subarray?

Every non-empty subarray has exactly one ending position.

For a subarray ending at index i, there are only two possibilities:

1. It contains only nums[i]
2. It is created by extending a subarray ending at index i - 1

Therefore, every subarray is generated exactly once.

For example:

nums = [1, 2, 3]

The subarrays are grouped by their ending position.

Ending at index 0

[1]

Ending at index 1

[2] [1, 2]

Ending at index 2

[3] [2, 3] [1, 2, 3]

This covers every possible non-empty subarray exactly once.

Java Solution

class Solution {
    public int[] resultArray(int[] nums, int k) {
        int[] result = new int[k];
        int[] dp = new int[k];

        for (int num : nums) {
            int[] next = new int[k];

            int value = num % k;

            // Start a new subarray with only num
            next[value]++;

            // Extend all previous subarrays
            for (int r = 0; r < k; r++) {
                if (dp[r] > 0) {
                    int newRemainder = (r * value) % k;
                    next[newRemainder] += dp[r];
                }
            }

            // Add all subarrays ending at the current position
            for (int r = 0; r < k; r++) {
                result[r] += next[r];
            }

            // Move to the next position
            dp = next;
        }

        return result;
    }
}

Java Code Explanation

result

int[] result = new int[k];

result[r] stores the total number of subarrays found so far whose product modulo k is r.

dp

int[] dp = new int[k];

dp[r] stores the number of subarrays ending at the previous index with product remainder r.

next

int[] next = new int[k];

next stores the subarrays ending at the current index.

Current Value

int value = num % k;

Only the remainder of num matters because we only care about the final product modulo k.

Start a New Subarray

next[value]++;

This represents the subarray containing only the current element:

[num]

Extend Previous Subarrays

for (int r = 0; r < k; r++) {
    if (dp[r] > 0) {
        int newRemainder = (r * value) % k;
        next[newRemainder] += dp[r];
    }
}

For every possible previous remainder:

1. Take the old remainder r
2. Multiply it by the current value
3. Take modulo k
4. Add the number of matching previous subarrays

This lets us process many subarrays at once.

Update the Answer

for (int r = 0; r < k; r++) {
    result[r] += next[r];
}

Every subarray ending at the current position should contribute to the final result.

Move to the Next Position

dp = next;

The current subarrays become the previous subarrays for the next iteration.

Time Complexity

For every element in nums, we iterate over all k possible remainders.

Therefore:

O(n * k)

where:

• n = length of nums
• k = divisor

Because the constraint says:

k <= 5

the algorithm is effectively close to:

O(n)

Space Complexity

We use arrays of size k:

• result
• dp
• next

Therefore:

O(k)

Since:

k <= 5

the extra space is effectively constant:

O(1)

Final Intuition

The problem can be reduced to:

Find every non-empty contiguous subarray, calculate its product modulo k, and count how many produce each remainder.

Checking every subarray individually is too slow.

Instead, we keep a DP array containing:

How many subarrays ending at the previous index have each possible product remainder.

For every new number:

1. Start a new subarray with that number.
2. Extend every previous subarray.
3. Calculate the new product remainder using modulo arithmetic.
4. Add the new counts to the final answer.
5. Make next the new dp.

The key formula is:

newRemainder = (oldRemainder * (num % k)) % k

Because k <= 5, there are only a few remainder states to track, making the solution efficient.

Complexity Summary

With k <= 5:

• Time is effectively O(n)
• Extra space is effectively O(1)

Key Takeaway

The most important idea in this problem is:

Prefix and suffix removal leaves a contiguous subarray, so the problem becomes counting the product modulo k for every non-empty subarray.

Instead of explicitly generating all subarrays, dynamic programming groups subarrays by their product remainder, reducing the complexity from O(n²) to O(n * k).

Instruction-by-Instruction Breakdown :