3525 LeetCode problem solution

LeetCode problem link: 3525. Find X Value of Array II


LeetCode 3525 problem description

This is Hard level 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 subarray1 that starts from the beginning of the array and extends to any point within it.

A suffix of an array is a subarray1 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.


1. A subarray is a contiguous sequence of elements within an array.


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

LeetCode 3525 problem: solution explanation

The solution combines three patterns: Segment Tree for dynamic point updates and range queries, Prefix Product for counting all valid arrays after removing a suffix, and Modular Arithmetic for reducing every product to one of only k possible remainders.

! This is a short theoretical description. Below is an example with each code block explained.


The main pattern is a Segment Tree because each query performs a point update and then asks for information about the range [start, n - 1].

After removing nums[0..start - 1], removing a suffix leaves one of these arrays:

nums[start]
nums[start..start + 1]
nums[start..start + 2]
...
nums[start..n - 1]

This turns the problem into a Prefix Product problem: for the range [start, n - 1], we need to count how many prefix products have remainder x modulo k.

Since k <= 5, we can use Modular Arithmetic technique (like previous problem - 3524. Find X Value of Array I) and store only the possible remainders 0..k - 1 instead of the actual products.

For every Segment Tree node, store:

prod - the product of the entire segment modulo k.
cnt[r] - the number of non-empty prefixes of the segment whose product has remainder r.

For a single element nums[i]:

r = nums[i] % k

prod = r
cnt[r] = 1

To merge two adjacent segments left and right, first keep all prefix products that end inside left: result.cnt[r] += left.cnt[r]

A prefix that reaches the right segment contains the entire left segment followed by a prefix of right.

If a prefix of right has remainder r, its remainder in the combined segment becomes newRemainder = (left.prod * r) % k.

Therefore result.cnt[newRemainder] += right.cnt[r].

The product of the complete merged segment is: result.prod = (left.prod * right.prod) % k.

For every query [index, value, start, x], first update nums[index] = value in the Segment Tree. Then query the range [start, n - 1] and return cnt[x].


LeetCode 3525 problem: Example

Suppose:

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

For a query with:

start = 1
x = 2

after removing the prefix before start, the array is:

[3, 4]

The possible remaining arrays after removing a suffix are:

[3]
[3, 4]

Their products modulo 5 are:

3 % 5 = 3

(3 * 4) % 5 = 12 % 5 = 2

So the remainder counts are:

remainder 0 is 0
remainder 1 is 0
remainder 2 is 1
remainder 3 is 1
remainder 4 is 0

For x = 2, the answer is 1.

If the query updates an element first, we update that position in the Segment Tree and then perform the same range query using the new value.


Step-by-step

Node structure

Each segment tree node stores the product of its entire segment modulo k and the number of non-empty prefixes for every possible remainder. Since k <= 5, cnt uses a fixed-size array.

struct Node {
  int prod = 1;
  array<int, 5> cnt{};
};

Merge two segments

When two adjacent segments are merged, all prefixes from the left segment remain unchanged. A prefix from the right segment becomes a prefix of the combined segment only after the entire left segment is included, so its remainder is multiplied by left.prod.

Node mergeNodes(const Node& left, const Node& right) {
  Node res;
  res.prod = (left.prod * right.prod) % k;

  for(int r = 0; r < k; r++) res.cnt[r] += left.cnt[r];

  for(int r = 0; r < k; r++) {
    int nr = (left.prod * r) % k;
    res.cnt[nr] += right.cnt[r];
  }

  return res;
}

Build the Segment Tree

For a leaf, the segment contains one element, so it has exactly one non-empty prefix. Internal nodes are built by merging their left and right children.

void build(int node, int l, int r, const vector<int>& nums) {
  if(l == r) {
    int rem = nums[l] % k;
    tree[node].prod = rem;
    tree[node].cnt[rem] = 1;

    return;
  }

  int mid = l + (r - l) / 2;

  build(node * 2, l, mid, nums);
  build(node * 2 + 1, mid + 1, r, nums);

  tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
}

Update an element

Each query permanently changes nums[index]. The corresponding leaf is replaced with the new remainder, then all nodes on the path back to the root are recomputed.

void update(int node, int l, int r, int index, int value) {
  if(l == r) {
    tree[node] = Node{};

    int rem = value % k;
    tree[node].prod = rem;
    tree[node].cnt[rem] = 1;

    return;
  }

  int mid = l + (r - l) / 2;

  if(index <= mid) update(node * 2, l, mid, index, value);
  else update(node * 2 + 1, mid + 1, r, index, value);

  tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
}

Query the remaining range

After removing nums[0..start - 1], the relevant range is [start, n - 1]. The Segment Tree returns the prefix-product information for exactly this range while preserving the original left-to-right order.

Node query(int node, int l, int r, int ql, int qr) {
  if(ql <= l && r <= qr) return tree[node];

  int mid = l + (r - l) / 2;

  if(qr <= mid) return query(node * 2, l, mid, ql, qr);
  if(ql > mid) return query(node * 2 + 1, mid + 1, r, ql, qr);

  Node left = query(node * 2, l, mid, ql, qr);
  Node right = query(node * 2 + 1, mid + 1, r, ql, qr);

  return mergeNodes(left, right);
}

Process each query

First apply the permanent update. Then query [start, n - 1]. Every non-empty prefix of this range corresponds to one possible remaining array after removing a suffix, so res.cnt[x] is exactly the required x-value.

for(const auto& q : queries) {
  int index = q[0];
  int value = q[1];
  int start = q[2];
  int x = q[3];

  update(1, 0, n - 1, index, value);

  Node res = query(1, 0, n - 1, start, n - 1);
  result.push_back(res.cnt[x]);
}

LeetCode 3525 problem: complexity

Building the Segment Tree takes O(n * k). Each point update and range query takes O(k * log n). Since k <= 5, it is treated as a constant.


Overall:

Time complexity: O((n + q) * k * log n) = O(n + q * log n)
Space complexity: O(n * k) = O(n)

where q is the number of queries.


LeetCode 3525 C++ solution

class Solution {
  // Each node stores the product of the whole segment modulo k
  // and the number of prefixes for every possible remainder.
  struct Node {
    int prod = 1;
    array<int, 5> cnt{};
  };

  int n, k;
  vector<Node> tree;

  // Merge two adjacent segments.
  // Keep all prefixes from the left segment.
  // Prefixes from the right segment are multiplied by the full left product.
  Node mergeNodes(const Node& left, const Node& right) {
    Node res;
    res.prod = (left.prod * right.prod) % k;

    for(int r = 0; r < k; r++) res.cnt[r] += left.cnt[r];

    for(int r = 0; r < k; r++) {
      int nr = (left.prod * r) % k;
      res.cnt[nr] += right.cnt[r];
    }

    return res;
  }

  // Build the segment tree.
  // A leaf has exactly one non-empty prefix: the element itself.
  void build(int node, int l, int r, const vector<int>& nums) {
    if(l == r) {
      int rem = nums[l] % k;
      tree[node].prod = rem;
      tree[node].cnt[rem] = 1;

      return;
    }

    int mid = l + (r - l) / 2;

    build(node * 2, l, mid, nums);
    build(node * 2 + 1, mid + 1, r, nums);

    tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
  }

    // Permanently update nums[index] and rebuild the affected tree nodes.
  void update(int node, int l, int r, int index, int value) {
    if(l == r) {
      tree[node] = Node{};

      int rem = value % k;
      tree[node].prod = rem;
      tree[node].cnt[rem] = 1;

      return;
    }

    int mid = l + (r - l) / 2;

    if(index <= mid) update(node * 2, l, mid, index, value);
    else update(node * 2 + 1, mid + 1, r, index, value);

    tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
  }

  // Return the combined information for range [ql, qr].
  // For each query this range is [start, n - 1].
  Node query(int node, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return tree[node];

    int mid = l + (r - l) / 2;

    if(qr <= mid) return query(node * 2, l, mid, ql, qr);
    if(ql > mid) return query(node * 2 + 1, mid + 1, r, ql, qr);

    Node left = query(node * 2, l, mid, ql, qr);
    Node right = query(node * 2 + 1, mid + 1, r, ql, qr);

    return mergeNodes(left, right);
  }

public:
  vector<int> resultArray(vector<int>& nums, int k, vector<vector<int>>& queries) {
    this->n = nums.size();
    this->k = k;

    // Build the tree for the initial array.
    tree.resize(4 * n);
    build(1, 0, n - 1, nums);

    vector<int> result;
    result.reserve(queries.size());

    // Apply each permanent update, then analyze nums[start..n - 1].
    for(const auto& q : queries) {
      int index = q[0];
      int value = q[1];
      int start = q[2];
      int x = q[3];

      update(1, 0, n - 1, index, value);

      // cnt[x] is the number of prefixes of nums[start..n - 1]
      // whose product modulo k equals x.
      Node res = query(1, 0, n - 1, start, n - 1);
      result.push_back(res.cnt[x]);
    }

    return result;
  }
};

LeetCode 3525 Java solution

class Solution {
  // Each node stores the product of the whole segment modulo k
  // and the number of prefixes for every possible remainder.
  static class Node {
    int prod = 1;
    int[] cnt = new int[5];
  }

  private Node[] tree;
  private int n, k;

  // Merge two adjacent segments.
  // Keep all prefixes from the left segment.
  // Prefixes from the right segment are multiplied by the full left product.
  private Node mergeNodes(Node left, Node right) {
    Node res = new Node();
    res.prod = (left.prod * right.prod) % k;

    for(int r = 0; r < k; r++) res.cnt[r] += left.cnt[r];

    for(int r = 0; r < k; r++) {
      int nr = (left.prod * r) % k;
      res.cnt[nr] += right.cnt[r];
    }

    return res;
  }

  // Build the segment tree.
  // A leaf has exactly one non-empty prefix: the element itself.
  private void build(int node, int l, int r, int[] nums) {
    if(l == r) {
      tree[node] = new Node();

      int rem = nums[l] % k;
      tree[node].prod = rem;
      tree[node].cnt[rem] = 1;

      return;
    }

    int mid = l + (r - l) / 2;

    build(node * 2, l, mid, nums);
    build(node * 2 + 1, mid + 1, r, nums);

    tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
  }

  // Permanently update nums[index] and rebuild the affected tree nodes.
  private void update(int node, int l, int r, int index, int value) {
    if(l == r) {
      tree[node] = new Node();

      int rem = value % k;
      tree[node].prod = rem;
      tree[node].cnt[rem] = 1;

      return;
    }

    int mid = l + (r - l) / 2;

    if(index <= mid) update(node * 2, l, mid, index, value);
    else update(node * 2 + 1, mid + 1, r, index, value);

    tree[node] = mergeNodes(tree[node * 2], tree[node * 2 + 1]);
  }

  // Return the combined information for range [ql, qr].
  // For each query this range is [start, n - 1].
  private Node query(int node, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return tree[node];

    int mid = l + (r - l) / 2;

    if(qr <= mid) return query(node * 2, l, mid, ql, qr);
    if(ql > mid) return query(node * 2 + 1, mid + 1, r, ql, qr);

    Node left = query(node * 2, l, mid, ql, qr);
    Node right = query(node * 2 + 1, mid + 1, r, ql, qr);

    return mergeNodes(left, right);
  }

  public int[] resultArray(int[] nums, int k, int[][] queries) {
    this.n = nums.length;
    this.k = k;

    // Build the tree for the initial array.
    tree = new Node[4 * n];
    build(1, 0, n - 1, nums);

    int[] result = new int[queries.length];

    // Apply each permanent update, then analyze nums[start..n - 1].
    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);

      // cnt[x] is the number of prefixes of nums[start..n - 1]
      // whose product modulo k equals x.
      Node res = query(1, 0, n - 1, start, n - 1);
      result[i] = res.cnt[x];
    }

    return result;
  }
}

LeetCode 3525 JavaScript solution

var resultArray = function(nums, k, queries) {
  const n = nums.length;

  // prod[node] stores the product of the whole segment modulo k.
  // cnt[r][node] stores the number of prefixes with remainder r.
  const prod = new Int32Array(4 * n);
  const cnt = Array.from({ length: 5 }, () => new Int32Array(4 * n));

  // Merge the two children into their parent.
  // Right prefixes are multiplied by the full product of the left segment.
  function pull(node) {
    const left = node * 2;
    const right = left + 1;

    prod[node] = (prod[left] * prod[right]) % k;

    for(let r = 0; r < k; r++) cnt[r][node] = cnt[r][left];

    for(let r = 0; r < k; r++) {
      const nr = (prod[left] * r) % k;
      cnt[nr][node] += cnt[r][right];
    }
  }

  // Build the segment tree.
  // A leaf has exactly one non-empty prefix: the element itself.
  function build(node, l, r) {
    if(l === r) {
      const rem = nums[l] % k;

      prod[node] = rem;
      cnt[rem][node] = 1;

      return;
    }

    const mid = (l + r) >> 1;

    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);

    pull(node);
  }

  // Permanently update nums[index] and rebuild the affected tree nodes.
  function update(node, l, r, index, value) {
    if(l === r) {
      for(let rem = 0; rem < k; rem++) cnt[rem][node] = 0;

      const rem = value % k;

      prod[node] = rem;
      cnt[rem][node] = 1;

      return;
    }

    const mid = (l + r) >> 1;

    if(index <= mid) update(node * 2, l, mid, index, value);
    else update(node * 2 + 1, mid + 1, r, index, value);

    pull(node);
  }

  // Return the combined information for range [ql, qr].
  // For each query this range is [start, n - 1].
  function query(node, l, r, ql, qr) {
    if(ql <= l && r <= qr) {
      const counts = new Int32Array(5);

      for(let rem = 0; rem < k; rem++) counts[rem] = cnt[rem][node];

      return [prod[node], counts];
    }

    const mid = (l + r) >> 1;

    if(qr <= mid) return query(node * 2, l, mid, ql, qr);
    if(ql > mid) return query(node * 2 + 1, mid + 1, r, ql, qr);

    const left = query(node * 2, l, mid, ql, qr);
    const right = query(node * 2 + 1, mid + 1, r, ql, qr);

    const counts = new Int32Array(5);

    for(let rem = 0; rem < k; rem++) counts[rem] += left[1][rem];

    for(let rem = 0; rem < k; rem++) {
      const nr = (left[0] * rem) % k;
      counts[nr] += right[1][rem];
    }

    return [(left[0] * right[0]) % k, counts];
  }

  // Build the tree for the initial array.
  build(1, 0, n - 1);

  const result = new Array(queries.length);

  // Apply each permanent update, then analyze nums[start..n - 1].
  for(let i = 0; i < queries.length; i++) {
    const [index, value, start, x] = queries[i];

    update(1, 0, n - 1, index, value);

    // counts[x] is the number of prefixes of nums[start..n - 1]
    // whose product modulo k equals x.
    const res = query(1, 0, n - 1, start, n - 1);
    result[i] = res[1][x];
  }

  return result;
};

LeetCode 3525 TypeScript solution

function resultArray(nums: number[], k: number, queries: number[][]): number[] {
  const n = nums.length;

  // prod[node] stores the product of the whole segment modulo k.
  // cnt[r][node] stores the number of prefixes with remainder r.
  const prod = new Int32Array(4 * n);
  const cnt: Int32Array[] = Array.from({ length: 5 }, () => new Int32Array(4 * n));

  // Merge the two children into their parent.
  // Right prefixes are multiplied by the full product of the left segment.
  function pull(node: number): void {
    const left = node * 2;
    const right = left + 1;

    prod[node] = (prod[left] * prod[right]) % k;

    for(let r = 0; r < k; r++) cnt[r][node] = cnt[r][left];

    for(let r = 0; r < k; r++) {
      const nr = (prod[left] * r) % k;
      cnt[nr][node] += cnt[r][right];
    }
  }

  // Build the segment tree.
  // A leaf has exactly one non-empty prefix: the element itself.
  function build(node: number, l: number, r: number): void {
    if(l === r) {
      const rem = nums[l] % k;

      prod[node] = rem;
      cnt[rem][node] = 1;
      
      return;
    }

    const mid = (l + r) >> 1;

    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);

    pull(node);
  }

  // Permanently update nums[index] and rebuild the affected tree nodes.
  function update(node: number, l: number, r: number, index: number, value: number): void {
    if(l === r) {
      for(let rem = 0; rem < k; rem++) cnt[rem][node] = 0;

      const rem = value % k;

      prod[node] = rem;
      cnt[rem][node] = 1;

      return;
    }

    const mid = (l + r) >> 1;

    if(index <= mid) update(node * 2, l, mid, index, value);
    else update(node * 2 + 1, mid + 1, r, index, value);

    pull(node);
  }

  // Return the combined information for range [ql, qr].
  // For each query this range is [start, n - 1].
  function query(node: number, l: number, r: number, ql: number, qr: number): [number, Int32Array] {
    if(ql <= l && r <= qr) {
      const counts = new Int32Array(5);

      for(let rem = 0; rem < k; rem++) counts[rem] = cnt[rem][node];

      return [prod[node], counts];
    }

    const mid = (l + r) >> 1;

    if(qr <= mid) return query(node * 2, l, mid, ql, qr);
    if(ql > mid) return query(node * 2 + 1, mid + 1, r, ql, qr);

    const left = query(node * 2, l, mid, ql, qr);
    const right = query(node * 2 + 1, mid + 1, r, ql, qr);

    const counts = new Int32Array(5);

    for(let rem = 0; rem < k; rem++) counts[rem] += left[1][rem];

    for(let rem = 0; rem < k; rem++) {
      const nr = (left[0] * rem) % k;
      counts[nr] += right[1][rem];
    }

    return [(left[0] * right[0]) % k, counts];
  }

  // Build the tree for the initial array.
  build(1, 0, n - 1);

  const result: number[] = new Array(queries.length);

  // Apply each permanent update, then analyze nums[start..n - 1].
  for(let i = 0; i < queries.length; i++) {
    const [index, value, start, x] = queries[i];

    update(1, 0, n - 1, index, value);

    // counts[x] is the number of prefixes of nums[start..n - 1]
    // whose product modulo k equals x.
    const res = query(1, 0, n - 1, start, n - 1);
    result[i] = res[1][x];
  }

  return result;
}

LeetCode 3525 Python solution

from typing import List

class Solution:
  def resultArray(self, nums: List[int], k: int, queries: List[List[int]]) -> List[int]:
    n = len(nums)

    # prod[node] stores the product of the whole segment modulo k.
    # cnt[r][node] stores the number of prefixes with remainder r.
    prod = [1] * (4 * n)
    cnt = [[0] * (4 * n) for _ in range(5)]

    # Merge the two children into their parent.
    # Right prefixes are multiplied by the full product of the left segment.
    def pull(node):
      left = node * 2
      right = left + 1

      prod[node] = (prod[left] * prod[right]) % k

      for r in range(k): cnt[r][node] = cnt[r][left]

      for r in range(k):
        nr = (prod[left] * r) % k
        cnt[nr][node] += cnt[r][right]

    # Build the segment tree.
    # A leaf has exactly one non-empty prefix: the element itself.
    def build(node, l, r):
      if l == r:
        rem = nums[l] % k

        prod[node] = rem
        cnt[rem][node] = 1

        return

      mid = (l + r) // 2

      build(node * 2, l, mid)
      build(node * 2 + 1, mid + 1, r)

      pull(node)

    # Permanently update nums[index] and rebuild the affected tree nodes.
    def update(node, l, r, index, value):
      if l == r:
        for rem in range(k): cnt[rem][node] = 0

        rem = value % k

        prod[node] = rem
        cnt[rem][node] = 1

        return

      mid = (l + r) // 2

      if index <= mid: update(node * 2, l, mid, index, value)
      else: update(node * 2 + 1, mid + 1, r, index, value)

      pull(node)

    # Merge two query results in their original left-to-right order.
    def merge(left, right):
      left_prod, left_cnt = left
      right_prod, right_cnt = right

      counts = left_cnt[:]

      for r in range(k):
        nr = (left_prod * r) % k
        counts[nr] += right_cnt[r]

      return (left_prod * right_prod) % k, counts

    # Return the combined information for range [ql, qr].
    # For each query this range is [start, n - 1].
    def query(node, l, r, ql, qr):
      if ql <= l and r <= qr: return prod[node], [cnt[x][node] for x in range(k)]

      mid = (l + r) // 2

      if qr <= mid: return query(node * 2, l, mid, ql, qr)

      if ql > mid: return query(node * 2 + 1, mid + 1, r, ql, qr)

      left = query(node * 2, l, mid, ql, qr)
      right = query(node * 2 + 1, mid + 1, r, ql, qr)

      return merge(left, right)

    # Build the tree for the initial array.
    build(1, 0, n - 1)

    result = []

    # Apply each permanent update, then analyze nums[start..n - 1].
    for index, value, start, x in queries:
      update(1, 0, n - 1, index, value)

      # counts[x] is the number of prefixes of nums[start..n - 1]
      # whose product modulo k equals x.
      _, counts = query(1, 0, n - 1, start, n - 1)
      result.append(counts[x])

    return result