How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Bytedance during technical interviews.

Count Special Subarrays by Modular Frequency

Quick Overview

This question evaluates the ability to apply modular arithmetic, frequency tracking, and prefix-count reasoning to efficiently count subarrays that satisfy a congruence condition, testing algorithmic problem-solving and scalable complexity management.

Company: Bytedance

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given an integer array `nums`, and two integers `modulo` and `target`, where `0 <= target < modulo`. Call an index `i` **special** if `nums[i] % modulo == target`. A contiguous subarray `nums[l..r]` is considered **valid** if the number of special indices inside the subarray has remainder `target` when divided by `modulo`. Return the number of valid subarrays. **Example** ```text nums = [3, 1, 9, 6], modulo = 3, target = 0 ``` Special indices are those whose values are divisible by `3`: indices `0`, `2`, and `3`. Valid subarrays are those where the count of special elements is congruent to `0 mod 3`. **Requirements** - Design an efficient algorithm. - The array may be large, so an `O(n^2)` enumeration of all subarrays is not acceptable. - Return the count as a 64-bit integer.

Quick Answer: This question evaluates the ability to apply modular arithmetic, frequency tracking, and prefix-count reasoning to efficiently count subarrays that satisfy a congruence condition, testing algorithmic problem-solving and scalable complexity management.

You are given an integer array nums and two integers modulo and target, where 0 <= target < modulo. An index i is special if nums[i] modulo modulo equals target. A contiguous non-empty subarray nums[l..r] is valid if the number of special indices inside that subarray has remainder target when divided by modulo. Return the number of valid subarrays. The array may be large, so checking every subarray is too slow.

Constraints

0 <= len(nums) <= 200000
1 <= modulo <= 1000000000
0 <= target < modulo
-1000000000 <= nums[i] <= 1000000000
Use the mathematical non-negative remainder for modulo comparisons

Examples

Input: ([3, 1, 9, 6], 3, 0)

Expected Output: 2

Explanation: The special elements are 3, 9, and 6. Valid subarrays are [3, 1, 9, 6] with 3 special elements and [1] with 0 special elements; both counts are congruent to 0 mod 3.

Input: ([1, 4, 2, 7, 10], 3, 1)

Expected Output: 7

Explanation: Special elements are those congruent to 1 mod 3. There are 7 subarrays whose number of special elements is congruent to 1 mod 3.

Input: ([1, 2, 4], 3, 0)

Expected Output: 6

Explanation: There are no special elements, so every non-empty subarray has 0 special elements, which is congruent to 0 mod 3.

Input: ([], 5, 2)

Expected Output: 0

Explanation: An empty array has no non-empty subarrays.

Input: ([5, -2, 0], 1, 0)

Expected Output: 6

Explanation: Modulo 1, every value has remainder 0 and every special count is congruent to 0 mod 1, so all 6 non-empty subarrays are valid.

Input: ([-1, 2, 5], 3, 2)

Expected Output: 2

Explanation: All three values have remainder 2 mod 3, so each is special. Valid subarrays must contain 2 special elements modulo 3, which are the two length-2 subarrays.

Input: ([2, 2, 2, 2], 2, 0)

Expected Output: 4

Explanation: All elements are special. A subarray is valid when it has an even number of elements. There are 3 length-2 subarrays and 1 length-4 subarray.

Hints

Convert the array into a sequence of 0s and 1s, where 1 means the index is special.
For each prefix count modulo modulo, count how many previous prefix remainders would make the subarray's special count congruent to target.

Quick Overview