Count Residue Prefixes · Interview Problem

Leetcode

count-residue-prefixes

Medium

Hash Maps

Prefix Sums

Modulo Arithmetic

Count Residue Prefixes

Given an array of integers and a modulus value k, count the number of prefix subarrays whose sum modulo k matches a certain residue.

Acceptance 50%

Start Practice

Problem Statement

Core description from the backend problem record.

Description

You are given an array of integers nums and an integer k. A prefix subarray is defined as any subarray that starts from index 0 and extends to some index i (0 <= i < nums.length). Your task is to count how many prefix subarrays have a sum that when taken modulo k equals a specified residue value r.

Input Format

The first line contains two integers n and k, where n is the length of the array, and k is the modulus value.
The second line contains n integers representing the elements of the array nums.
The third line contains a single integer r, the residue to match.

Output Format

Print a single integer representing the count of prefix subarrays where (sum of elements) mod k equals r.

Constraints

1 <= n <= 10^5
1 <= k <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= r < k

Examples

Sample cases returned by the problem API.

Example 1

Input

5 3
1 2 3 4 1
0

Output

Explanation

Prefix sums modulo 3 are: [1, 0, 0, 1, 2]. Prefixes with modulo 0 are at indices 1 and 2, so count is 2.

Loading Preptin

Description

Input Format

Output Format

Constraints