K divisible elements subarrays

Array Hash Table Trie Rolling Hash Hash Function Enumeration

54.8% acceptance

Feb 25, 2026

737

162

Given an integer array nums and two integers k and p, return the number of distinct subarrays, which have at most k elements that are divisible by p. Two arrays nums1 and nums2 are said to be distinct if: They are of different lengths, or There exists at least one index i where nums1[i] != nums2[i]. A subarray is defined as a non-empty contiguous sequence of elements in an array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_distinct(nums: Vec<i32>, k: i32, p: i32) -> i32 {
    use std::collections::HashSet;
    let n = nums.len();
    let mut seen: HashSet<Vec<i32>> = HashSet::new();
    for i in 0..n {
      let mut cnt = 0;
      for j in i..n {
        if nums[j] % p == 0 { cnt += 1; }
        if cnt > k { break; }
        seen.insert(nums[i..=j].to_vec());
      }
    }
    seen.len() as i32
  }
}