# Find X Value of Array I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-x-value-of-array-i)
Canonical: https://scaleengineer.com/dsa/problems/find-x-value-of-array-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
You are given an array of **positive** integers `nums`, and a **positive** integer `k`.

You are allowed to perform an operation **once** on `nums`, where in each operation you can remove any **non-overlapping** prefix and suffix from `nums` such that `nums` remains **non-empty**.

You need to find the **x-value** of `nums`, which is the number of ways to perform this operation so that the **product** of the remaining elements leaves a _remainder_ of `x` when divided by `k`.

Return an array `result` of size `k` where `result[x]` is the **x-value** of `nums` for `0 <= x <= k - 1`.

A **prefix** of an array is a subarray that starts from the beginning of the array and extends to any point within it.

A **suffix** of an array is a subarray that starts at any point within the array and extends to the end of the array.

**Note** that the prefix and suffix to be chosen for the operation can be **empty**.

**Example 1:**

**Input:** nums = \[1,2,3,4,5\], k = 3

**Output:** \[9,2,4\]

**Explanation:**

* For `x = 0`, the possible operations include all possible ways to remove non-overlapping prefix/suffix that do not remove `nums[2] == 3`.
* For `x = 1`, the possible operations are:  
  * Remove the empty prefix and the suffix `[2, 3, 4, 5]`. `nums` becomes `[1]`.
  * Remove the prefix `[1, 2, 3]` and the suffix `[5]`. `nums` becomes `[4]`.
* For `x = 2`, the possible operations are:  
  * Remove the empty prefix and the suffix `[3, 4, 5]`. `nums` becomes `[1, 2]`.
  * Remove the prefix `[1]` and the suffix `[3, 4, 5]`. `nums` becomes `[2]`.
  * Remove the prefix `[1, 2, 3]` and the empty suffix. `nums` becomes `[4, 5]`.
  * Remove the prefix `[1, 2, 3, 4]` and the empty suffix. `nums` becomes `[5]`.

**Example 2:**

**Input:** nums = \[1,2,4,8,16,32\], k = 4

**Output:** \[18,1,2,0\]

**Explanation:**

* For `x = 0`, the only operations that **do not** result in `x = 0` are:  
  * Remove the empty prefix and the suffix `[4, 8, 16, 32]`. `nums` becomes `[1, 2]`.
  * Remove the empty prefix and the suffix `[2, 4, 8, 16, 32]`. `nums` becomes `[1]`.
  * Remove the prefix `[1]` and the suffix `[4, 8, 16, 32]`. `nums` becomes `[2]`.
* For `x = 1`, the only possible operation is:  
  * Remove the empty prefix and the suffix `[2, 4, 8, 16, 32]`. `nums` becomes `[1]`.
* For `x = 2`, the possible operations are:  
  * Remove the empty prefix and the suffix `[4, 8, 16, 32]`. `nums` becomes `[1, 2]`.
  * Remove the prefix `[1]` and the suffix `[4, 8, 16, 32]`. `nums` becomes `[2]`.
* For `x = 3`, there is no possible way to perform the operation.

**Example 3:**

**Input:** nums = \[1,1,2,1,1\], k = 2

**Output:** \[9,6\]

**Constraints:**

* `1 <= nums[i] <= 109`
* `1 <= nums.length <= 105`
* `1 <= k <= 5`

# Approaches
## Brute Force by Iterating All Subarrays
This approach is the most straightforward and directly follows the problem description. It involves generating every possible non-empty subarray of `nums`, calculating the product of its elements modulo `k`, and then incrementing a counter for the corresponding remainder. This method is simple to conceptualize but computationally very expensive.
**Time:** O(N³), where N is the number of elements in `nums`. There are O(N²) subarrays. For each subarray, calculating the product takes, on average, O(N) time, leading to a cubic time complexity. · **Space:** O(k). We only need an array of size `k` to store the results. Given `k` is small, this is effectively O(1).
**Pros:** Simple to understand and implement.; Directly translates the problem statement into code.
**Cons:** Extremely inefficient due to three nested loops.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The core idea is to systematically check every single subarray. A subarray can be defined by its start and end indices, let's say `i` and `j`. We can use a pair of nested loops to iterate through all possible values of `i` and `j` where `0 <= i <= j < nums.length`.

For each such subarray `nums[i...j]`, we need to compute the product of its elements. A third, inner loop is used for this purpose. To prevent the product from becoming excessively large and causing overflow, we apply the modulo `k` operation at each step of the multiplication. After computing the final product modulo `k` for a subarray, we increment the corresponding counter in our result array.

```java
class Solution {
    public int[] findXValue(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[k];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                long product = 1;
                // Calculate product for subarray nums[i...j]
                for (int l = i; l <= j; l++) {
                    product = (product * nums[l]) % k;
                }
                result[(int)product]++;
            }
        }
        return result;
    }
}
```
### Algorithm
*   Initialize a result array `res` of size `k` to all zeros.
*   Iterate through all possible start indices `l` from `0` to `n-1`.
*   For each `l`, iterate through all possible end indices `r` from `l` to `n-1`.
*   For each subarray `nums[l...r]`:
    *   Initialize a `product` variable to 1.
    *   Iterate from `i = l` to `r`, updating the product: `product = (product * nums[i]) % k`.
    *   Increment the count in `res` for the calculated remainder: `res[product]++`.
*   Return `res`.

## Optimized Brute Force with Running Product
This approach improves upon the naive brute-force method by eliminating redundant calculations. Instead of re-calculating the product for each subarray from scratch, we can compute it incrementally. For a fixed starting point `l`, as we extend the subarray to the right by incrementing `r`, the product of the new subarray `nums[l...r]` can be found by simply multiplying the product of the previous subarray `nums[l...r-1]` with the new element `nums[r]`.
**Time:** O(N²). Two nested loops iterate through all O(N²) subarrays, and the work inside the inner loop is now O(1). · **Space:** O(k). We only need an array of size `k` to store the results.
**Pros:** More efficient than the O(N³) approach.; Still relatively easy to understand and implement.
**Cons:** Still too slow for the given constraints (`N <= 10^5`) and will result in TLE.
### Explanation
We use two nested loops. The outer loop fixes the starting index `i` of the subarrays. The inner loop iterates from `i` to the end of the array, defining the ending index `j`. Inside the inner loop, we maintain a `currentProduct` variable. For each `j`, we update `currentProduct` by multiplying it with `nums[j]` (and taking the modulo `k`). This `currentProduct` represents the product of the subarray `nums[i...j]`. We then use this value to update our result array. This optimization removes the third, innermost loop from the previous approach, reducing the complexity from cubic to quadratic.

```java
class Solution {
    public int[] findXValue(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[k];
        for (int i = 0; i < n; i++) {
            long currentProduct = 1;
            for (int j = i; j < n; j++) {
                currentProduct = (currentProduct * nums[j]) % k;
                result[(int)currentProduct]++;
            }
        }
        return result;
    }
}
```
### Algorithm
*   Initialize a result array `res` of size `k` to all zeros.
*   Iterate through all possible start indices `l` from `0` to `n-1`.
*   For each `l`, initialize a `current_product = 1`.
*   Iterate through all possible end indices `r` from `l` to `n-1`.
*   Update `current_product` by multiplying with `nums[r]` modulo `k`.
*   Increment the count in `res` for the `current_product`.
*   Return `res`.

## Dynamic Programming with Remainder Frequencies
This is the most efficient approach, which uses dynamic programming. The key insight is that we can build up the solution by processing the array one element at a time. At each index `i`, we can calculate the product remainders for all subarrays ending at `i` by using the information we computed for subarrays ending at the previous index `i-1`. Since `k` is very small, this becomes highly efficient.
**Time:** O(N * k). We iterate through the N elements of `nums`. For each element, we perform a loop of size `k` to update frequencies. Since `k` is a small constant, the complexity is effectively linear in N. · **Space:** O(k). We use a few arrays of size `k` (`result`, `prev_freq`, `current_freq`). Since `k` is very small (`k <= 5`), this is effectively constant space.
**Pros:** Highly efficient and optimal for the given constraints.; Passes within the time limits.
**Cons:** The logic is more complex than the brute-force approaches.; Requires careful handling of potential integer overflows for the counts, as the total number of subarrays can be very large. Using `long` for counts is necessary.
### Explanation
We iterate through `nums`, and for each element `num`, we maintain a frequency map (an array of size `k`) called `currentFreq`. `currentFreq[x]` will store the number of subarrays ending at the current element `num` whose product modulo `k` is `x`.

For each `num`, `currentFreq` is computed as follows:
1.  A new subarray consisting of just `num` is formed. Its product remainder is `num % k`. So, we initialize `currentFreq[num % k]` to 1.
2.  We then consider extending all subarrays that ended at the *previous* element. Let's say `prevFreq` stored the frequencies for the previous element. For each remainder `p` from `0` to `k-1`, there were `prevFreq[p]` subarrays. When we append `num` to them, they form new subarrays with a product remainder of `(p * (num % k)) % k`. We add `prevFreq[p]` to the count for this new remainder in `currentFreq`.

After computing `currentFreq` for the current `num`, we add its counts to our global `result` array. Then, `currentFreq` becomes `prevFreq` for the next iteration.

Note: The total number of subarrays can be up to `10^5 * (10^5 + 1) / 2`, which is about `5 * 10^9`. This means the counts can exceed the capacity of a 32-bit integer. Therefore, we must use `long` for our frequency and result arrays to avoid overflow.

```java
class Solution {
    public int[] findXValue(int[] nums, int k) {
        // Use long for counts to prevent overflow, as total subarrays can be large.
        long[] result = new long[k];
        // prevFreq[rem] stores the count of subarrays ending at the previous element
        // with a product remainder of 'rem'.
        long[] prevFreq = new long[k];

        for (int num : nums) {
            long[] currentFreq = new long[k];
            int val = num % k;

            // Case 1: The subarray consists of only the current element `num`.
            currentFreq[val]++;

            // Case 2: Extend all subarrays ending at the previous element.
            for (int p = 0; p < k; p++) {
                if (prevFreq[p] > 0) {
                    int newRem = (p * val) % k;
                    currentFreq[newRem] += prevFreq[p];
                }
            }

            // Add the counts from subarrays ending at the current element to the total result.
            for (int x = 0; x < k; x++) {
                result[x] += currentFreq[x];
            }

            // The current frequencies become the previous frequencies for the next iteration.
            prevFreq = currentFreq;
        }
        
        // Cast the long results to int as per typical problem constraints.
        int[] finalResult = new int[k];
        for (int i = 0; i < k; i++) {
            finalResult[i] = (int) result[i];
        }
        return finalResult;
    }
}
```
### Algorithm
*   Initialize a `long` result array `res` of size `k` to all zeros.
*   Initialize a `long` array `prev_freq` of size `k` to all zeros. This will store remainder frequencies for subarrays ending at the previous element.
*   Iterate through each `num` in the input array `nums`.
*   For each `num`, create a new `long` array `current_freq` of size `k`.
*   Let `v = num % k`.
*   Increment `current_freq[v]` by 1. This accounts for the subarray containing only `num`.
*   Iterate `p` from `0` to `k-1`. For each `p`, if `prev_freq[p]` is greater than 0, it means there are `prev_freq[p]` subarrays ending at the previous element with remainder `p`. Extending them with `num` gives a new remainder `(p * v) % k`. Add `prev_freq[p]` to `current_freq[(p * v) % k]`.
*   Add the counts from `current_freq` to the total `res` array.
*   Update `prev_freq` to `current_freq` for the next iteration.
*   After the loop, cast the `long` result array to an `int` array and return it.