Count of Interesting Subarrays - Practice Coding Problems

Count of Interesting Subarrays - Problem

You are given a 0-indexed integer array nums, an integer modulo, and an integer k.

Your task is to find the count of subarrays that are interesting.

A subarray nums[l..r] is interesting if the following condition holds:

Let cnt be the number of indices i in the range [l, r] such that nums[i] % modulo == k. Then, cnt % modulo == k.

Return an integer denoting the count of interesting subarrays.

Note: A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Subarrays: [4] has 1 element where 4%3=1, and 1%3=1 ✓. [2,4] has 1 element where 4%3=1, and 1%3=1 ✓. [3,2,4] has 1 element where 4%3=1, and 1%3=1 ✓. Total: 3 interesting subarrays.

Example 2 — Multiple Valid Elements

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

› Output: 4

💡 Note: Looking for elements where nums[i]%3=2: positions 0,2,3,5 have value 2. We need subarrays where count%3=2. Subarrays with exactly 2 or 5 such elements work.

Example 3 — No Valid Subarrays

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

› Output: 0

💡 Note: No element satisfies nums[i]%4=3, so no subarray can have count%4=3. Result is 0.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁹
1 ≤ modulo ≤ 10⁹
0 ≤ k < modulo

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [3,2,4], modulo=3, k=1. Find elements where nums[i]%3=1

Identify Pattern

Only element 4 satisfies condition (4%3=1)

Count Subarrays

Find subarrays where count of valid elements % 3 = 1

Key Takeaway

🎯 Key Insight: Transform to prefix sum problem and use hash map to track remainder patterns efficiently

Asked in

G Google 12 M Microsoft 8 A Amazon 6

The key insight is to transform this into a prefix sum problem where we track remainder patterns. Convert the array to binary (1 if nums[i] % modulo == k, else 0), then use hash map to count subarrays efficiently. Best approach is prefix sum with hash map. Time: O(n), Space: O(min(n, modulo))

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum with Hash Map	O(n)	O(min(n, modulo))	Use prefix sum to track remainder patterns efficiently
Brute Force - Check All Subarrays	O(n³)	O(1)	Check every possible subarray and count valid elements

Prefix Sum with Hash Map — Algorithm Steps

Convert elements to 1 if nums[i] % modulo == k, else 0
Calculate prefix sums
Use hash map to count subarrays where (prefix[j] - prefix[i]) % modulo == k

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert & Track

Convert to binary and track prefix sum remainders

Hash Map Lookup

Find previous prefixes with matching remainder pattern

Count Subarrays

Add count of valid subarray endings at each position

Code -

solution.c — C

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

#define HASH_SIZE 100003

typedef struct HashNode {
    int key;
    int value;
    struct HashNode* next;
} HashNode;

int hash(int key) {
    return (key % HASH_SIZE + HASH_SIZE) % HASH_SIZE;
}

void put(HashNode* table[], int key, int value) {
    int idx = hash(key);
    HashNode* node = table[idx];
    while (node) {
        if (node->key == key) {
            node->value = value;
            return;
        }
        node = node->next;
    }
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = table[idx];
    table[idx] = newNode;
}

int get(HashNode* table[], int key) {
    int idx = hash(key);
    HashNode* node = table[idx];
    while (node) {
        if (node->key == key) {
            return node->value;
        }
        node = node->next;
    }
    return 0;
}

long long solution(int* nums, int numsSize, int modulo, int k) {
    long long result = 0;
    
    // Convert to binary array: 1 if nums[i] % modulo == k, else 0
    int prefixSum = 0;
    // Hash table: remainder -> count of prefix sums with that remainder
    HashNode* remainderCount[HASH_SIZE] = {NULL};
    put(remainderCount, 0, 1); // Empty prefix
    
    for (int i = 0; i < numsSize; i++) {
        // Add 1 if current element satisfies condition
        if (nums[i] % modulo == k) {
            prefixSum += 1;
        }
        
        // Current remainder
        int currentRemainder = prefixSum % modulo;
        
        // We want subarrays where count % modulo == k
        // If current prefix has remainder r, we need previous prefix with remainder (r - k) % modulo
        int targetRemainder = (currentRemainder - k) % modulo;
        if (targetRemainder < 0) targetRemainder += modulo;
        
        // Add count of previous prefixes with target remainder
        result += get(remainderCount, targetRemainder);
        
        // Add current remainder to map
        put(remainderCount, currentRemainder, get(remainderCount, currentRemainder) + 1);
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int num = atoi(token);
        if (num != 0 || token[0] == '0') {
            nums[numsSize++] = num;
        }
        token = strtok(NULL, "[,]");
    }
    
    int modulo, k;
    scanf("%d", &modulo);
    scanf("%d", &k);
    
    long long result = solution(nums, numsSize, modulo, k);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array with O(1) hash map operations

✓ Linear Growth

Space Complexity

O(min(n, modulo))

Hash map stores at most 'modulo' different remainder values

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

456 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

Prefix Sum with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler