Find X Value of Array I - Practice Coding Problems

Find X Value of Array I - 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.

Note: 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. The prefix and suffix to be chosen for the operation can be empty.

Input & Output

Example 1 — Basic Case

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

› Output: [0,1,2,1,2]

💡 Note: All possible subarrays: [2]→2%5=2, [2,3]→6%5=1, [2,3,4]→24%5=4, [3]→3%5=3, [3,4]→12%5=2, [4]→4%5=4. Count: remainder 0 appears 0 times, remainder 1 appears 1 time, remainder 2 appears 2 times, remainder 3 appears 1 time, remainder 4 appears 2 times.

Example 2 — Single Element

$ Input: nums = [7], k = 3

› Output: [0,1,0]

💡 Note: Only one subarray [7]: 7 % 3 = 1. So remainder 1 appears once, others appear 0 times.

Example 3 — Multiple of k

$ Input: nums = [2,5], k = 10

› Output: [1,0,1,0,0,1,0,0,0,0]

💡 Note: Subarrays: [2]→2%10=2, [2,5]→10%10=0, [5]→5%10=5. Count: remainder 0, 2, 5 each appear once.

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ nums[i] ≤ 10⁹
2 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [2,3,4] and k=5

Generate All Subarrays

Find all contiguous subarrays and calculate product mod k

Count by Remainder

Group and count by remainder values 0 through k-1

Key Takeaway

🎯 Key Insight: Generate all contiguous subarrays and count occurrences of each product remainder

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we need to count all possible contiguous subarrays and group them by their product remainder when divided by k. The optimal approach uses nested loops with running products to achieve O(n²) time complexity and O(1) extra space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subarrays	O(n³)	O(1)	Generate all possible subarrays by removing prefixes and suffixes, calculate products
Optimized - Two Loops with Running Product	O(n²)	O(1)	Calculate products incrementally while iterating, avoiding redundant multiplications

Brute Force - Try All Subarrays — Algorithm Steps

Iterate through all possible left boundaries i
For each i, iterate through all possible right boundaries j >= i
Calculate product of subarray nums[i...j]
Find remainder when product is divided by k
Increment count for that remainder

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Try all combinations of start and end positions

Calculate Products

For each subarray, compute product mod k

Count Remainders

Track frequency of each remainder value

Code -

solution.c — C

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

void solution(int* nums, int numsSize, int k, int* result) {
    for (int i = 0; i < k; i++) {
        result[i] = 0;
    }
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            long long product = 1;
            for (int idx = i; idx <= j; idx++) {
                product = (product * nums[idx]) % k;
            }
            result[product]++;
        }
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int* result = (int*)malloc(k * sizeof(int));
    solution(nums, numsSize, k, result);
    
    printf("[");
    for (int i = 0; i < k; i++) {
        printf("%d", result[i]);
        if (i < k - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops for i and j (O(n²)) and inner loop to calculate product (O(n))

⚠ Quadratic Growth

Space Complexity

O(1)

Only using result array of size k and a few variables

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

567 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 - Try All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler