Count Distinct Subarrays Divisible by K in Sorted Array Python/Java solution

Python and Java implementations typically compute prefix sums first, then iterate over all start and end indices. For each valid subarray where sum % k == 0, insert the sequence (or its hash) into a set. The final answer is the size of the set containing unique valid subarrays.

What is the best approach for Count Distinct Subarrays Divisible by K in Sorted Array?

The most practical approach uses prefix sums combined with a hash set. Prefix sums allow constant-time calculation of any subarray sum, while the set ensures only distinct subarrays are counted. This reduces the brute force O(n^3) solution to about O(n^2) time with O(n^2) space.

Is Count Distinct Subarrays Divisible by K in Sorted Array asked at Google/Amazon/Meta?

Variants involving prefix sums and modulo arithmetic frequently appear in interviews at companies like Google, Amazon, and Meta. Problems such as counting subarrays divisible by K or detecting equal prefix remainders test understanding of prefix sums and hash maps.

What data structure is used in Count Distinct Subarrays Divisible by K in Sorted Array?

The core data structures are prefix sum arrays and a hash set. Prefix sums provide constant-time range sum queries, while the hash set stores subarray representations or hashes to guarantee distinctness.

What is the time complexity of Count Distinct Subarrays Divisible by K in Sorted Array?

The optimized approach runs in O(n^2) time because every pair of start and end indices may still need to be checked. Prefix sums make each range-sum calculation O(1). Additional space up to O(n^2) can be required to store distinct subarrays or their hashes.

Description Hints 3 Solution Video 14:25

3729. Count Distinct Subarrays Divisible by K in Sorted Array

Q: Is Count Distinct Subarrays Divisible by K in Sorted Array easy or hard?

The problem is categorized as Hard because it combines two concepts: modular prefix sums and distinct subarray detection. Handling duplicates efficiently while keeping the algorithm within O(n^2) requires careful use of hashing and prefix techniques.

Q: How to solve Count Distinct Subarrays Divisible by K in Sorted Array in O(n)?

An O(n) solution generally does not exist because the number of possible subarrays itself is O(n^2). Even with prefix modulo tricks, you must still verify distinct sequences. The practical improvement focuses on O(n^2) with prefix sums and hashing to keep each check constant time.

Hard27.4% acceptance

You are given an integer array nums sorted in non-descending order and a positive integer k.

A subarray of nums is good if the sum of its elements is divisible by k.

Return an integer denoting the number of distinct good subarrays of nums.

Subarrays are distinct if their sequences of values are. For example, there are 3 distinct subarrays in [1, 1, 1], namely [1], [1, 1], and [1, 1, 1].

Example 1:

Input: nums = [1,2,3], k = 3

Output: 3

Explanation:

The good subarrays are [1, 2], [3], and [1, 2, 3]. For example, [1, 2, 3] is good because the sum of its elements is 1 + 2 + 3 = 6, and 6 % k = 6 % 3 = 0.

Example 2:

Input: nums = [2,2,2,2,2,2], k = 6

Output: 2

Explanation:

The good subarrays are [2, 2, 2] and [2, 2, 2, 2, 2, 2]. For example, [2, 2, 2] is good because the sum of its elements is 2 + 2 + 2 = 6, and 6 % k = 6 % 6 = 0.

Note that [2, 2, 2] is counted only once.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
nums is sorted in non-descending order.
1 <= k <= 10⁹

Topics

Hints open one at a time

Hint 1

Use prefix sums.

Hint 2

Any subarray with >= 2 distinct values has a unique strict-increase boundary (i, j), so the value sequence is identified by that boundary and how many elements you take from each edge.

Hint 3

Count single-value sequences per run by testing (L*val) % k == 0.

14:25

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def numGoodSubarrays(self, nums: List[int], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,3]
3

Input

[2,2,2,2,2,2]
6

Your code is saved on this device.Solution