3524. Find X Value of Array I LeetCode Solution

Last updated: April 22, 2025

In this guide, you will get 3524. Find X Value of Array I LeetCode Solution with the best time and space complexity. The solution to Find X Value of Array I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find X Value of Array I solution in C++
Find X Value of Array I solution in Java
Find X Value of Array I solution in Python
Additional Resources

3524. Find X Value of Array I LeetCode Solution image

Problem Statement of Find X Value of Array I

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

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n)

3524. Find X Value of Array I LeetCode Solution in C++

class Solution {
 public:
  vector<long long> resultArray(vector<int>& nums, int k) {
    vector<long long> ans(k);
    // dp[r] := the number of subarrays ending at current position with
    // product % k == r
    vector<long long> dp(k);

    for (const int num : nums) {
      vector<long long> newDp(k);
      const int numMod = num % k;
      // Start new subarray with only `num`.
      newDp[numMod] = 1;
      // Extend all previous subarrays.
      for (int i = 0; i < k; ++i) {
        const int newMod = (static_cast<long>(i) * numMod) % k;
        newDp[newMod] += dp[i];
      }
      // Accumulate counts into ans.
      for (int i = 0; i < k; ++i)
        ans[i] += newDp[i];
      dp = std::move(newDp);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3524. Find X Value of Array I LeetCode Solution in Java

class Solution {
  public long[] resultArray(int[] nums, int k) {
    long[] ans = new long[k];
    // dp[r] := the number of subarrays ending at current position with
    // product % k == r
    long[] dp = new long[k];

    for (final int num : nums) {
      long[] newDp = new long[k];
      final int numMod = num % k;
      // Start new subarray with only `num`.
      newDp[numMod] = 1;
      // Extend all previous subarrays.
      for (int i = 0; i < k; ++i) {
        final int newMod = (int) (1L * i * numMod % k);
        newDp[newMod] += dp[i];
      }
      // Accumulate counts into ans.
      for (int i = 0; i < k; ++i)
        ans[i] += newDp[i];
      dp = newDp;
    }

    return ans;
  }
}
// code provided by PROGIEZ

3524. Find X Value of Array I LeetCode Solution in Python

class Solution:
  def resultArray(self, nums: list[int], k: int) -> list[int]:
    ans = [0] * k
    # dp[r] := the number of subarrays ending at current position with
    # product % k == r
    dp = [0] * k

    for num in nums:
      newDp = [0] * k
      numMod = num % k
      # Start new subarray with only `num`
      newDp[numMod] = 1
      # Extend all previous subarrays
      for i in range(k):
        newMod = (i * numMod) % k
        newDp[newMod] += dp[i]
      # Accumulate counts into ans
      for i in range(k):
        ans[i] += newDp[i]
      dp = newDp

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents