3524 LeetCode problem solution

LeetCode problem link: 3524. Find X Value of Array I


LeetCode 3524 problem description

This is Medium level 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 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.


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


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

LeetCode 3524 problem: solution explanation

After removing a prefix and a suffix, the remaining elements always form a non-empty contiguous subarray. Therefore, the problem is equivalent to counting all subarrays by the remainder of their product modulo k.

Since k <= 5, we can use dynamic programming with only k states. While scanning nums from left to right, let dp[r] be the number of subarrays that end at the previous position and whose product has remainder r modulo k.

For the current value num, every previous subarray can be extended by num. If its old remainder is r, the new remainder is:

i = (num % k)
(r * i) % k

We also start a new subarray containing only num. After computing the new states, add their counts to result.

Because there are only k remainder states, the time complexity is O(n * k) and the extra space complexity is O(k).


LeetCode 3524 problem: example

Suppose:

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

All possible remaining non-empty subarrays are:

[1]       product = 1 is remainder 1 because 1 % 3 = 1
[2]       product = 2 is remainder 2 because 2 % 3 = 2
[3]       product = 3 is remainder 0 because 3 % 3 = 0
[1, 2]    product = 2 (1 * 2) is remainder 2 because 2 % 3 = 2
[2, 3]    product = 6 (2 * 3) is remainder 0 because 6 % 3 = 0
[1, 2, 3] product = 6 (1 * 2 * 3) is remainder 0 because 6 % 3 = 0

So:

remainder 0 are: [3], [2, 3], [1, 2, 3] = 3 times
remainder 1 is: [1] = 1 time
remainder 2 are [2], [1, 2] = 2 times

Therefore:

result[0] = 3
result[1] = 1
result[2] = 2

and the answer is:

[3, 1, 2]

The DP builds exactly these subarrays by grouping them according to their product remainder instead of calculating every product separately.


LeetCode 3524 problem: complexity

  • Time complexity: O(n * k)
  • Space complexity: O(k)

Since k <= 5, this is effectively linear in nums.length.


LeetCode 3524 C++ solution

class Solution {
public:
  vector<long long> resultArray(vector<int>& nums, int k) {
    vector<long long> result(k, 0);
    vector<long long> dp(k, 0);

    for(int num : nums)
    {
      vector<long long> next(k, 0);
      int value = num % k;

      // Start a new subarray.
      next[value]++;

      // Extend all subarrays ending at the previous position.
      for(int r = 0; r < k; r++)
      {
        int newRemainder = (r * value) % k;
        next[newRemainder] += dp[r];
      }

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

      dp = move(next);
    }

    return result;
  }
};

LeetCode Java C++ solution

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

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

      // Start a new subarray.
      next[value]++;

      // Extend all subarrays ending at the previous position.
      for(int r = 0; r < k; r++) {
        int newRemainder = (r * value) % k;
        next[newRemainder] += dp[r];
      }

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

      dp = next;
    }

    return result;
  }
}

LeetCode 3524 JavaScript solution

var resultArray = function(nums, k) {
  const result = Array(k).fill(0);
  let dp = Array(k).fill(0);

  for(const num of nums) {
    const next = Array(k).fill(0);
    const value = num % k;

    // Start a new subarray.
    next[value]++;

    // Extend all subarrays ending at the previous position.
    for(let r = 0; r < k; r++) {
      const newRemainder = (r * value) % k;
      next[newRemainder] += dp[r];
    }

    for(let r = 0; r < k; r++) result[r] += next[r];

    dp = next;
  }

  return result;
};

LeetCode 3524 TypeScript solution

function resultArray(nums: number[], k: number): number[] {
  const result: number[] = new Array(k).fill(0);
  let dp: number[] = new Array(k).fill(0);

  for(const num of nums) {
    const next: number[] = new Array(k).fill(0);
    const value = num % k;

    // Start a new subarray.
    next[value]++;

    // Extend all subarrays ending at the previous position.
    for(let r = 0; r < k; r++) {
      const newRemainder = (r * value) % k;
      next[newRemainder] += dp[r];
    }

    for(let r = 0; r < k; r++) result[r] += next[r];

    dp = next;
  }

  return result;
}

LeetCode 3524 Python solution

from typing import List

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

    for num in nums:
      nxt = [0] * k
      value = num % k

      # Start a new subarray.
      nxt[value] += 1

      # Extend all subarrays ending at the previous position.
      for r in range(k):
        new_remainder = (r * value) % k
        nxt[new_remainder] += dp[r]

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

      dp = nxt

    return result