LeetCode 2845. Count of Interesting Subarrays Solution in Java, C++, Python & More | Explanation + Code

Description

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.

 

Example 1:

Input: nums = [3,2,4], modulo = 2, k = 1
Output: 3
Explanation: In this example the interesting subarrays are: 
The subarray nums[0..0] which is [3]. 
- There is only one index, i = 0, in the range [0, 0] that satisfies nums[i] % modulo == k. 
- Hence, cnt = 1 and cnt % modulo == k.  
The subarray nums[0..1] which is [3,2].
- There is only one index, i = 0, in the range [0, 1] that satisfies nums[i] % modulo == k.  
- Hence, cnt = 1 and cnt % modulo == k.
The subarray nums[0..2] which is [3,2,4]. 
- There is only one index, i = 0, in the range [0, 2] that satisfies nums[i] % modulo == k. 
- Hence, cnt = 1 and cnt % modulo == k. 
It can be shown that there are no other interesting subarrays. So, the answer is 3.

Example 2:

Input: nums = [3,1,9,6], modulo = 3, k = 0
Output: 2
Explanation: In this example the interesting subarrays are: 
The subarray nums[0..3] which is [3,1,9,6]. 
- There are three indices, i = 0, 2, 3, in the range [0, 3] that satisfy nums[i] % modulo == k. 
- Hence, cnt = 3 and cnt % modulo == k. 
The subarray nums[1..1] which is [1]. 
- There is no index, i, in the range [1, 1] that satisfies nums[i] % modulo == k. 
- Hence, cnt = 0 and cnt % modulo == k. 
It can be shown that there are no other interesting subarrays. So, the answer is 2.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= modulo <= 109
• 0 <= k < modulo

Solutions

Solution 1: Hash Table + Prefix Sum

The problem requires the number of indices i in an interval that satisfy nums[i] \bmod modulo = k. We can transform the array nums into a 0-1 array arr, where arr[i] = 1 indicates nums[i] \bmod modulo = k, otherwise arr[i] = 0.

For an interval [l, r], we can calculate the number of 1s in arr[l..r] through the prefix sum array s, i.e., s[r] - s[l - 1], where s[0] = 0.

We use a hash table cnt to record the number of occurrences of the prefix sum s \bmod modulo, initially cnt[0]=1.

Next, we traverse the array arr, calculate the prefix sum s, add the number of occurrences of (s-k) \bmod modulo to the answer, and then add 1 to the number of occurrences of s \bmod modulo.

After the traversal ends, return the answer.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

PythonJavaC++GoTypeScriptRust

class Solution: def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int: arr = [int(x % modulo == k) for x in nums] cnt = Counter() cnt[0] = 1 ans = s = 0 for x in arr: s += x ans += cnt[(s - k) % modulo] cnt[s % modulo] += 1 return ans(code-box)

class Solution { public long countInterestingSubarrays(List<Integer> nums, int modulo, int k) { int n = nums.size(); int[] arr = new int[n]; for (int i = 0; i < n; ++i) { arr[i] = nums.get(i) % modulo == k ? 1 : 0; } Map<Integer, Integer> cnt = new HashMap<>(); cnt.put(0, 1); long ans = 0; int s = 0; for (int x : arr) { s += x; ans += cnt.getOrDefault((s - k + modulo) % modulo, 0); cnt.merge(s % modulo, 1, Integer::sum); } return ans; } }(code-box)

class Solution { public: long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) { int n = nums.size(); vector<int> arr(n); for (int i = 0; i < n; ++i) { arr[i] = int(nums[i] % modulo == k); } unordered_map<int, int> cnt; cnt[0] = 1; long long ans = 0; int s = 0; for (int x : arr) { s += x; ans += cnt[(s - k + modulo) % modulo]; cnt[s % modulo]++; } return ans; } };(code-box)

func countInterestingSubarrays(nums []int, modulo int, k int) (ans int64) { arr := make([]int, len(nums)) for i, x := range nums { if x%modulo == k { arr[i] = 1 } } cnt := map[int]int{} cnt[0] = 1 s := 0 for _, x := range arr { s += x ans += int64(cnt[(s-k+modulo)%modulo]) cnt[s%modulo]++ } return }(code-box)

function countInterestingSubarrays(nums: number[], modulo: number, k: number): number { const arr: number[] = []; for (const x of nums) { arr.push(x % modulo === k ? 1 : 0); } const cnt: Map<number, number> = new Map(); cnt.set(0, 1); let ans = 0; let s = 0; for (const x of arr) { s += x; ans += cnt.get((s - k + modulo) % modulo) || 0; cnt.set(s % modulo, (cnt.get(s % modulo) || 0) + 1); } return ans; }(code-box)

use std::collections::HashMap; impl Solution { pub fn count_interesting_subarrays(nums: Vec<i32>, modulo: i32, k: i32) -> i64 { let mut arr: Vec<i32> = nums .iter() .map(|&x| if x % modulo == k { 1 } else { 0 }) .collect(); let mut cnt: HashMap<i32, i64> = HashMap::new(); cnt.insert(0, 1); let mut ans: i64 = 0; let mut s: i32 = 0; for x in arr { s += x; let key = (s - k).rem_euclid(modulo); ans += *cnt.get(&key).unwrap_or(&0); *cnt.entry(s % modulo).or_insert(0) += 1; } ans } }(code-box)