Find X Value of Array I solution and explanation
The 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 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 removenums[2] == 3. - For
x = 1, the possible operations are:- Remove the empty prefix and the suffix
[2, 3, 4, 5].numsbecomes[1]. - Remove the prefix
[1, 2, 3]and the suffix[5].numsbecomes[4].
- Remove the empty prefix and the suffix
- For
x = 2, the possible operations are:- Remove the empty prefix and the suffix
[3, 4, 5].numsbecomes[1, 2]. - Remove the prefix
[1]and the suffix[3, 4, 5].numsbecomes[2]. - Remove the prefix
[1, 2, 3]and the empty suffix.numsbecomes[4, 5]. - Remove the prefix
[1, 2, 3, 4]and the empty suffix.numsbecomes[5].
- Remove the empty prefix and the suffix
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 inx = 0are:- Remove the empty prefix and the suffix
[4, 8, 16, 32].numsbecomes[1, 2]. - Remove the empty prefix and the suffix
[2, 4, 8, 16, 32].numsbecomes[1]. - Remove the prefix
[1]and the suffix[4, 8, 16, 32].numsbecomes[2].
- Remove the empty prefix and the suffix
- For
x = 1, the only possible operation is:- Remove the empty prefix and the suffix
[2, 4, 8, 16, 32].numsbecomes[1].
- Remove the empty prefix and the suffix
- For
x = 2, the possible operations are:- Remove the empty prefix and the suffix
[4, 8, 16, 32].numsbecomes[1, 2]. - Remove the prefix
[1]and the suffix[4, 8, 16, 32].numsbecomes[2].
- Remove the empty prefix and the suffix
- 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] <= 1091 <= nums.length <= 1051 <= k <= 5
Approach overview
Problem Overview: You are given an integer array and must compute its X value, a score derived from selecting elements in order while applying a mathematical contribution rule based on previously chosen elements. The challenge is choosing elements so the final score is maximized.
Approach 1: Brute Force Subsequence Enumeration (O(2^n) time, O(n) space)
The most direct way is to generate every possible subsequence of the array and compute the resulting X value for each one. During recursion, track how many elements have already been chosen and update the score contribution when adding the next element. This guarantees the optimal result because all possibilities are explored. The downside is exponential growth: each element has a "take" or "skip" decision, resulting in 2^n states. This approach mainly helps verify correctness for small inputs and clarifies how the scoring rule works.
Approach 2: Dynamic Programming on Prefixes (O(n^2) time, O(n^2) space)
Instead of recomputing every subsequence, store intermediate results. Let dp[i][k] represent the maximum score using the first i elements while selecting exactly k elements. When processing element i, either skip it or include it as the k-th chosen value and update the score using the mathematical contribution rule. The recurrence builds from previously computed prefixes, eliminating redundant recomputation. This transforms the exponential search into polynomial time. The approach combines ideas from Dynamic Programming and sequential array processing.
Approach 3: Optimized DP with Prefix Best (O(n) time, O(n) space)
The quadratic DP can be optimized by noticing that transitions depend only on the best previous state for a given selection count. Maintain a running best value while iterating through the array and update the next state in constant time. Each element contributes based on how many elements were previously selected, which can be tracked with prefix aggregates instead of a full table. This reduces the state transition cost dramatically. The result is a linear scan with dynamic updates, combining Array traversal and mathematical observation from Math properties of the scoring formula.
Recommended for interviews: Start by explaining the brute force subsequence idea to show understanding of the decision space. Then move to the DP formulation that stores prefix results. Interviewers typically expect the optimized DP solution because it demonstrates pattern recognition, state compression, and the ability to reduce an O(n^2) transition to O(n).
Solution
Thinking
Removing a prefix and a suffix leaves one subarray; we need how many have product
\equiv x \pmod k.n \le 10^5andk \le 5, so DP on remainders replaces enumeration.Let
f[i][r]be the number of subarrays ending atiwhose product isrmodulok. Transfer fromf[i-1]by multiplyingnums[i], and start a new subarray ati. Summing by remainder fillsresult.
After removing any non-overlapping prefix and suffix, the remainder is a non-empty subarray. The task is to count subarrays whose product modulo k equals 0, 1, ldots, k-1.
Let f[r] be the number of subarrays ending at the current index whose product is r modulo k. Scan x = nums[i] from left to right and use g for the new ending-at-i state: move each f[r] to g[(r times x) bmod k], then add the singleton subarray [x] into g[x bmod k]. Add g into the answer and set f \leftarrow g.
The time complexity is O(n times k) and the space complexity is O(k), where n is the length of nums.
class Solution:
def resultArray(self, nums: list[int], k: int) -> list[int]:
ans = [0] * k
f = [0] * k
for x in nums:
g = [0] * k
for r, cnt in enumerate(f):
g[r * x % k] += cnt
g[x % k] += 1
for r, cnt in enumerate(g):
ans[r] += cnt
f = g
return ansclass Solution {
public long[] resultArray(int[] nums, int k) {
long[] ans = new long[k];
long[] f = new long[k];
for (int x : nums) {
long[] g = new long[k];
for (int r = 0; r < k; ++r) {
g[(int) (1L * r * x % k)] += f[r];
}
g[x % k] += 1;
for (int r = 0; r < k; ++r) {
ans[r] += g[r];
}
f = g;
}
return ans;
}
}class Solution {
public:
vector<long long> resultArray(vector<int>& nums, int k) {
vector<long long> ans(k);
vector<long long> f(k);
for (int x : nums) {
vector<long long> g(k);
for (int r = 0; r < k; ++r) {
g[1LL * r * x % k] += f[r];
}
g[x % k] += 1;
for (int r = 0; r < k; ++r) {
ans[r] += g[r];
}
f.swap(g);
}
return ans;
}
};function resultArray(nums: number[], k: number): number[] {
const ans = Array(k).fill(0);
let f = Array(k).fill(0);
for (const x of nums) {
const g = Array(k).fill(0);
for (let r = 0; r < k; ++r) {
g[(r * x) % k] += f[r];
}
g[x % k] += 1;
for (let r = 0; r < k; ++r) {
ans[r] += g[r];
}
f = g;
}
return ans;
}func resultArray(nums []int, k int) []int64 {
ans := make([]int64, k)
f := make([]int64, k)
for _, x := range nums {
g := make([]int64, k)
for r, cnt := range f {
g[r*x%k] += cnt
}
g[x%k]++
for r, cnt := range g {
ans[r] += cnt
}
f = g
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Enumeration | O(2^n) | O(n) | Conceptual understanding or very small arrays |
| Dynamic Programming on Prefixes | O(n^2) | O(n^2) | General case when deriving the recurrence and validating transitions |
| Optimized DP with Prefix Best | O(n) | O(n) | Interview-ready optimal solution for large inputs |
Frequently asked questions
Is Find X Value of Array I easy or hard?
Find X Value of Array I is generally considered a medium difficulty problem. The main challenge is identifying the correct dynamic programming state and recognizing how to optimize the transition using prefix information to reach linear time complexity.
Find X Value of Array I Python/Java solution
The implementation typically builds a DP array and iterates through the input once while updating the best achievable score. The same logic works across Python, Java, C++, and Go because it relies only on array traversal and constant-time state updates.
How to solve Find X Value of Array I in O(n)?
Maintain a running DP state that represents the best score achievable after selecting a certain number of elements. As you iterate through the array, update the contribution of the current element using prefix best values instead of scanning all previous states. This converts the DP transition into constant time per element, producing an O(n) algorithm.
What is the best approach for Find X Value of Array I?
The best approach uses dynamic programming with prefix optimization. By tracking the best score achievable for previously selected elements and updating it while scanning the array, the X value can be computed in O(n) time with O(n) space. This avoids the quadratic transitions of a naive DP table.
Is Find X Value of Array I asked at Google/Amazon/Meta?
Problems involving array scoring rules and dynamic programming transitions are common in interviews at companies like Google, Amazon, and Meta. Variants often appear where candidates must derive the correct DP state and then optimize it using prefix tracking or mathematical observations.
What data structure is used in Find X Value of Array I?
The core data structure is a dynamic programming array that stores the best score for prefixes of the input. During optimization, prefix aggregates or running maximum values are maintained to avoid scanning previous states repeatedly.
What is the time complexity of Find X Value of Array I?
The optimal solution runs in O(n) time and O(n) space. A straightforward dynamic programming formulation takes O(n^2) time because it evaluates transitions for every pair of positions, while brute force enumeration of subsequences requires O(2^n) time.