Katkat
Back

Count Special Subarrays by Modular Frequency

ByteDanceMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

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.

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

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.