Find X Value of Array I

Med

#3135Time: 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).1 company

Patterns

Math Dynamic Programming

Data structures

Array

Companies

Rubrik

Prompt

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] <= 10⁹
1 <= nums.length <= 10⁵
1 <= k <= 5

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int[] findXValue(int[] nums, int k) {3        int n = nums.length;4        int[] result = new int[k];5        for (int i = 0; i < n; i++) {6            for (int j = i; j < n; j++) {7                long product = 1;8                // Calculate product for subarray nums[i...j]9                for (int l = i; l <= j; l++) {10                    product = (product * nums[l]) % k;11                }12                result[(int)product]++;13            }14        }15        return result;16    }17}

Complexity

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

Trade-offs

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.

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

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.

Walkthrough

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.

1class Solution {2    public int[] findXValue(int[] nums, int k) {3        int n = nums.length;4        int[] result = new int[k];5        for (int i = 0; i < n; i++) {6            long currentProduct = 1;7            for (int j = i; j < n; j++) {8                currentProduct = (currentProduct * nums[j]) % k;9                result[(int)currentProduct]++;10            }11        }12        return result;13    }14}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

A new subarray consisting of just num is formed. Its product remainder is num % k. So, we initialize currentFreq[num % k] to 1.
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.

1class Solution {2    public int[] findXValue(int[] nums, int k) {3        // Use long for counts to prevent overflow, as total subarrays can be large.4        long[] result = new long[k];5        // prevFreq[rem] stores the count of subarrays ending at the previous element6        // with a product remainder of 'rem'.7        long[] prevFreq = new long[k];8 9        for (int num : nums) {10            long[] currentFreq = new long[k];11            int val = num % k;12 13            // Case 1: The subarray consists of only the current element `num`.14            currentFreq[val]++;15 16            // Case 2: Extend all subarrays ending at the previous element.17            for (int p = 0; p < k; p++) {18                if (prevFreq[p] > 0) {19                    int newRem = (p * val) % k;20                    currentFreq[newRem] += prevFreq[p];21                }22            }23 24            // Add the counts from subarrays ending at the current element to the total result.25            for (int x = 0; x < k; x++) {26                result[x] += currentFreq[x];27            }28 29            // The current frequencies become the previous frequencies for the next iteration.30            prevFreq = currentFreq;31        }32        33        // Cast the long results to int as per typical problem constraints.34        int[] finalResult = new int[k];35        for (int i = 0; i < k; i++) {36            finalResult[i] = (int) result[i];37        }38        return finalResult;39    }40}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem