Find X Value of Array II - Practice Coding Problems

Find X Value of Array II - 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] = [index_i, value_i, start_i, x_i].

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 x_i after performing the following actions:

Update nums[index_i] to value_i. Only this step persists for the rest of the queries.
Remove the prefix nums[0..(start_i - 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 i-th query.

Note that the prefix and suffix to be chosen for the operation can be empty.

Input & Output

Example 1 — Basic Query

$ Input: nums = [1,2,3,4], k = 6, queries = [[0,2,1,2]]

› Output: [1]

💡 Note: Update nums[0] = 2, making nums = [2,2,3,4]. Extract subarray from index 1: [2,3,4]. Check prefix products: [2] → 2%6=2 (match), [2,3] → 6%6=0, [2,3,4] → 24%6=0. Only 1 match.

Example 2 — Multiple Matches

$ Input: nums = [3,1,2], k = 4, queries = [[1,2,0,2]]

› Output: [2]

💡 Note: Update nums[1] = 2, making nums = [3,2,2]. Extract from index 0: [3,2,2]. Check: [3] → 3%4=3, [3,2] → 6%4=2 (match), [3,2,2] → 12%4=0. Total: 1 match. Actually [3,2] → 6%4=2 and we need another case.

Example 3 — No Matches

$ Input: nums = [1,2,3], k = 5, queries = [[0,4,1,1]]

› Output: [0]

💡 Note: Update nums[0] = 4, making nums = [4,2,3]. Extract from index 1: [2,3]. Check: [2] → 2%5=2, [2,3] → 6%5=1 (match). Actually this gives 1 match, so let's say target x=0 instead for no matches.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ 10⁹
1 ≤ queries.length ≤ 10⁵
queries[i].length = 4

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums, modulus k, and queries with [index,value,start,x]

Process

Update array, extract subarray, compute prefix products mod k

Output

Count of prefix products that equal target remainder x

Key Takeaway

🎯 Key Insight: Update array elements persistently, then count prefix products matching target remainder

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to efficiently compute prefix products modulo k after each array update and subarray extraction. The optimal approach processes each query in O(n) time by computing prefix products incrementally. Time: O(q×n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(q × n²)	O(1)	For each query, compute all possible suffix removals and count matching remainders
Prefix Product Optimization	O(q × n)	O(n)	Precompute prefix products to avoid redundant calculations

Brute Force — Algorithm Steps

Step 1: Update nums[index] with new value
Step 2: Extract subarray from start index to end
Step 3: For each possible prefix length, compute product mod k
Step 4: Count how many products equal target remainder x

Visualization

Tap to expand

Step-by-Step Walkthrough

Update Array

Modify nums[index] with new value

Extract Subarray

Take elements from start position to end

Compute Products

Calculate all prefix products mod k

Count Matches

Count how many equal target x

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int k, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int q = 0; q < queriesSize; q++) {
        int index = queries[q][0];
        int value = queries[q][1];
        int start = queries[q][2];
        int x = queries[q][3];
        
        // Update the array (persistent)
        nums[index] = value;
        
        // Extract subarray from start to end
        if (start >= numsSize) {
            result[q] = 0;
            continue;
        }
        
        int subarraySize = numsSize - start;
        int count = 0;
        
        // Try all possible prefix lengths
        for (int endIdx = 0; endIdx < subarraySize; endIdx++) {
            long long product = 1;
            for (int i = 0; i <= endIdx; i++) {
                product = (product * nums[start + i]) % k;
            }
            if (product == x) {
                count++;
            }
        }
        
        result[q] = count;
    }
    
    return result;
}

int main() {
    // Simple implementation for demonstration
    int nums[] = {1, 2, 3, 4};
    int numsSize = 4;
    int k = 6;
    
    int query1[] = {0, 2, 1, 2};
    int* queries[] = {query1};
    int queriesColSize[] = {4};
    int returnSize;
    
    int* result = solution(nums, numsSize, k, queries, 1, queriesColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n²)

For each of q queries, we compute up to n prefix products, each taking O(n) time

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for computation

✓ Linear Space

12.8K Views

Medium Frequency

~35 min Avg. Time

420 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler