# Find X Value of Array II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-x-value-of-array-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-x-value-of-array-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array, Segment Tree
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
You are given an array of **positive** integers `nums` and a **positive** integer `k`. You are also given a 2D array `queries`, where `queries[i] = [indexi, valuei, starti, xi]`.

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

The **x-value** of `nums` **for a given** `x` is defined as the number of ways to perform this operation so that the **product** of the remaining elements leaves a _remainder_ of `x` **modulo** `k`.

For each query in `queries` you need to determine the **x-value** of `nums` for `xi` after performing the following actions:

* Update `nums[indexi]` to `valuei`. Only this step persists for the rest of the queries.
* **Remove** the prefix `nums[0..(starti - 1)]` (where `nums[0..(-1)]` will be used to represent the **empty** prefix).

Return an array `result` of size `queries.length` where `result[i]` is the answer for the `ith` query.

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**.

**Note** that x-value has a _different_ definition in this version.

**Example 1:**

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

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

**Explanation:**

* For query 0, `nums` becomes `[1, 2, 2, 4, 5]`, and the empty prefix **must** be removed. The possible operations are:  
  * Remove the suffix `[2, 4, 5]`. `nums` becomes `[1, 2]`.
  * Remove the empty suffix. `nums` becomes `[1, 2, 2, 4, 5]` with a product 80, which gives remainder 2 when divided by 3.
* For query 1, `nums` becomes `[1, 2, 2, 3, 5]`, and the prefix `[1, 2, 2]` **must** be removed. The possible operations are:  
  * Remove the empty suffix. `nums` becomes `[3, 5]`.
  * Remove the suffix `[5]`. `nums` becomes `[3]`.
* For query 2, `nums` becomes `[1, 2, 2, 3, 5]`, and the empty prefix **must** be removed. The possible operations are:  
  * Remove the suffix `[2, 2, 3, 5]`. `nums` becomes `[1]`.
  * Remove the suffix `[3, 5]`. `nums` becomes `[1, 2, 2]`.

**Example 2:**

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

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

**Explanation:**

* For query 0, `nums` becomes `[2, 2, 4, 8, 16, 32]`. The only possible operation is:  
  * Remove the suffix `[2, 4, 8, 16, 32]`.
* For query 1, `nums` becomes `[2, 2, 4, 8, 16, 32]`. There is no possible way to perform the operation.

**Example 3:**

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

**Output:** \[5\]

**Constraints:**

* `1 <= nums[i] <= 109`
* `1 <= nums.length <= 105`
* `1 <= k <= 5`
* `1 <= queries.length <= 2 * 104`
* `queries[i] == [indexi, valuei, starti, xi]`
* `0 <= indexi <= nums.length - 1`
* `1 <= valuei <= 109`
* `0 <= starti <= nums.length - 1`
* `0 <= xi <= k - 1`

# Approaches
## Brute Force Simulation
For each query, we first perform the update on the `nums` array. Then, we simulate the process described in the problem. We iterate through all possible non-empty prefixes of the subarray `nums[start...]`, calculate their product modulo `k`, and count how many of them are equal to the target `x`.
**Time:** O(Q * N), where Q is the number of queries and N is the length of `nums`. For each of the Q queries, we might iterate through up to N elements. · **Space:** O(N) to store the `nums` array. If we exclude the storage for input and output, the auxiliary space complexity is O(1).
**Pros:** Simple to understand and implement.; Low memory overhead.
**Cons:** Highly inefficient due to re-computation for each query.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
This approach directly translates the problem statement into code. For every single query, it modifies the `nums` array and then iterates from the given `start` index to the end of the array. In this loop, it maintains a running product of the elements of the current prefix, takes it modulo `k`, and checks if it matches the query's `x` value. While straightforward, this method is computationally expensive because it re-calculates products for overlapping subproblems across different queries.

```java
class Solution {
    public int[] findXValue(int[] nums, int k, int[][] queries) {
        int[] result = new int[queries.length];
        long[] longNums = new long[nums.length];
        for (int i = 0; i < nums.length; i++) {
            longNums[i] = nums[i];
        }

        for (int i = 0; i < queries.length; i++) {
            int index = queries[i][0];
            int value = queries[i][1];
            int start = queries[i][2];
            int x = queries[i][3];

            longNums[index] = value;

            int count = 0;
            if (start < longNums.length) {
                long currentProduct = 1;
                for (int j = start; j < longNums.length; j++) {
                    currentProduct = (currentProduct * longNums[j]) % k;
                    if (currentProduct == x) {
                        count++;
                    }
                }
            }
            result[i] = count;
        }
        return result;
    }
}
```
### Algorithm
*   Initialize an empty list `results`.
*   For each query `[index, value, start, x]` in `queries`:
    *   Update `nums[index] = value`.
    *   Initialize `count = 0` and `current_product = 1`.
    *   Iterate with `j` from `start` to `nums.length - 1`.
        *   Update `current_product = (current_product * nums[j]) % k`.
        *   If `current_product == x`, increment `count`.
    *   Append `count` to `results`.
*   Return `results`.

## Segment Tree with Custom Merge Logic
A highly efficient approach using a Segment Tree data structure. Since queries involve point updates and range-like queries, a segment tree is a natural fit. The key is to design the segment tree nodes and the merge operation to handle the specific requirements of the problem, which involve prefix products modulo `k`.
**Time:** O(N*k + Q * k * log N). Building the tree takes `O(N*k)`. Each of the Q queries involves an update and a query, both taking `O(k * log N)` time. · **Space:** O(N * k) to store the segment tree. Each of the `O(N)` nodes stores an array of size `k`.
**Pros:** Very efficient for the given constraints.; Handles online updates and queries effectively with logarithmic time complexity per operation.
**Cons:** More complex to implement compared to the brute-force approach.; Higher constant factor in time complexity and uses more memory.
### Explanation
Each node in our segment tree will store two pieces of information for its corresponding range in the `nums` array:
1.  `prod`: The total product of all elements in the range, modulo `k`.
2.  `counts`: An array of size `k`. `counts[r]` stores the number of prefixes starting from the beginning of the node's range whose product modulo `k` is `r`.

The `merge` operation is crucial. When merging a `left` and `right` node, the new `prod` is simply `(left.prod * right.prod) % k`. The new `counts` array is formed by combining the `left.counts` with a transformed version of `right.counts`. Specifically, any prefix in the right child's range with product `p` contributes to a combined prefix with product `(left.prod * p) % k`. This allows us to efficiently calculate the required counts for any range.

An update changes a leaf and propagates up to the root by re-merging. A query for `nums[start...]` is a range query on the segment tree for `[start, N-1]`, which efficiently combines nodes to get the final counts.

```java
class Solution {
    class Node {
        long prod;
        long[] counts;

        Node(int k) {
            this.prod = 1;
            this.counts = new long[k];
        }
    }

    int k;
    long[] nums;
    Node[] tree;

    private Node merge(Node left, Node right) {
        Node res = new Node(k);
        res.prod = (left.prod * right.prod) % k;
        for (int i = 0; i < k; i++) {
            res.counts[i] = left.counts[i];
        }
        for (int i = 0; i < k; i++) {
            if (right.counts[i] > 0) {
                int newRem = (int) ((left.prod * i) % k);
                res.counts[newRem] += right.counts[i];
            }
        }
        return res;
    }

    private void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = new Node(k);
            tree[node].prod = nums[start] % k;
            tree[node].counts[(int)(nums[start] % k)] = 1;
            return;
        }
        int mid = start + (end - start) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }

    private void update(int node, int start, int end, int idx, long val) {
        if (start == end) {
            nums[idx] = val;
            tree[node] = new Node(k);
            tree[node].prod = val % k;
            tree[node].counts[(int)(val % k)] = 1;
            return;
        }
        int mid = start + (end - start) / 2;
        if (start <= idx && idx <= mid) {
            update(2 * node, start, mid, idx, val);
        } else {
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }

    private Node query(int node, int start, int end, int l, int r) {
        if (r < start || end < l || l > r) {
            return new Node(k); // Identity node
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = start + (end - start) / 2;
        Node p1 = query(2 * node, start, mid, l, r);
        Node p2 = query(2 * node + 1, mid + 1, end, l, r);
        return merge(p1, p2);
    }

    public int[] findXValue(int[] initialNums, int k, int[][] queries) {
        this.k = k;
        int n = initialNums.length;
        this.nums = new long[n];
        for(int i=0; i<n; ++i) this.nums[i] = initialNums[i];
        
        this.tree = new Node[4 * n];
        build(1, 0, n - 1);

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int index = queries[i][0];
            int value = queries[i][1];
            int start = queries[i][2];
            int x = queries[i][3];

            update(1, 0, n - 1, index, value);
            
            if (start >= n) {
                result[i] = 0;
            } else {
                Node resNode = query(1, 0, n - 1, start, n - 1);
                result[i] = (int) resNode.counts[x];
            }
        }
        return result;
    }
}
```
### Algorithm
*   Define a `Node` structure for the segment tree to store `prod` (product of elements in its range mod `k`) and `counts` (an array of size `k` for prefix product remainders).
*   Implement a `merge` function that combines two nodes. The new `prod` is the product of the children's `prod`s. The new `counts` are the `left` child's counts plus the `right` child's counts transformed by `left.prod`.
*   **Build**: Construct the segment tree from the initial `nums` array in `O(N*k)` time.
*   **For each query `[index, value, start, x]`**:
    *   **Update**: Perform a point update on the segment tree for `nums[index] = value`. This takes `O(k * log N)`.
    *   **Query**: Perform a range query on the segment tree for `[start, N-1]`. This also takes `O(k * log N)`. The result is a `Node` representing the entire range.
    *   The answer to the query is `result_node.counts[x]`.