K Divisible Elements Subarrays

Medium
1362.

K Divisible Elements Subarrays

K Divisible Elements Subarrays is a medium coding problem on arrays, hash table and enumeration, asked in Amazon and Google interviews.

Given an integer array nums and two integers k and p, return the number of distinct non-empty contiguous subarrays that contain at most k elements divisible by p.

Two subarrays are the same when they have the same length and the same values in the same order — where they occur in nums does not matter. For example, in [3,1,3] the two single-element subarrays [3] count once.

Example 1

Input
nums = [4,2,3,3], k = 1, p = 2
Output
6
Explanation
`[4]`, `[2]`, `[2,3]`, `[2,3,3]`, `[3]` and `[3,3]`. Any subarray holding both 4 and 2 has two even elements.

Example 2

Input
nums = [1,1,1], k = 1, p = 5
Output
3
Explanation
Nothing is divisible by 5, so all subarrays qualify, but only `[1]`, `[1,1]` and `[1,1,1]` are distinct.

Example 3

Input
nums = [6,3,6], k = 2, p = 3
Output
4
Explanation
`[6]`, `[3]`, `[6,3]` and `[3,6]`; the whole array has three multiples of 3.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i], p <= 200
  • 1 <= k <= nums.length

Follow-up: Can you solve it in O(n^2) time?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} p
 * @return {number}
 */
var countDistinct = function(nums, k, p) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

K Divisible Elements Subarrays — Problem & Solution

K Divisible Elements Subarrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

K Divisible Elements Subarrays is a medium coding problem on arrays, hash table and enumeration, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Enumeration, Trie
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer array nums and two integers k and p, return the number of distinct non-empty contiguous subarrays that contain at most k elements divisible by p.

Two subarrays are the same when they have the same length and the same values in the same order — where they occur in nums does not matter. For example, in [3,1,3] the two single-element subarrays [3] count once.

Example 1

Input: nums = [4,2,3,3], k = 1, p = 2
Output: 6
Explanation: `[4]`, `[2]`, `[2,3]`, `[2,3,3]`, `[3]` and `[3,3]`. Any subarray holding both 4 and 2 has two even elements.

Example 2

Input: nums = [1,1,1], k = 1, p = 5
Output: 3
Explanation: Nothing is divisible by 5, so all subarrays qualify, but only `[1]`, `[1,1]` and `[1,1,1]` are distinct.

Example 3

Input: nums = [6,3,6], k = 2, p = 3
Output: 4
Explanation: `[6]`, `[3]`, `[6,3]` and `[3,6]`; the whole array has three multiples of 3.

Constraints

  • 1 <= nums.length <= 200
  • 1 <= nums[i], p <= 200
  • 1 <= k <= nums.length

Follow-up: Can you solve it in O(n^2) time?

Hints for K Divisible Elements Subarrays

  1. Hint 1

    There are only about n^2 / 2 subarrays. For each start index, extend the end until the count of multiples of p exceeds k — after that, longer ones fail too.

  2. Hint 2

    The hard part is deduplication. Storing every subarray as a string costs O(n^3) in total.

  3. Hint 3

    Insert the subarrays that start at i into a trie, one value per edge, while you extend them. A subarray is new exactly when its last step creates a new trie node.

How to solve K Divisible Elements Subarrays

All subarrays starting at index i are prefixes of one another, so they are exactly the nodes along one path of a trie keyed by values. Counting newly created trie nodes counts distinct subarrays in O(n^2).

Approach

  1. Create a trie with an empty root.
  2. For each start i: set node = root and cnt = 0.
  3. For j = i, i+1, …: if nums[j] % p == 0, increment cnt; if cnt > k, stop extending this start.
  4. Follow (or create) the child of node labelled nums[j]. Creating it means the subarray nums[i..j] has never been seen — add 1 to the answer. Move node to that child.

Why it works

Each trie node at depth d stands for exactly one sequence of d values (the labels on its root path). Every valid subarray is inserted, and a node is created only the first time its sequence appears, so the number of created nodes equals the number of distinct valid subarrays. Stopping once cnt > k is safe because any extension keeps or increases the count.

Complexity

  • Time — O(n^2)
  • Space — O(n^2)

Pitfalls

  • Deduplicate by contents, not by position — [3] at index 0 and index 2 is one subarray.
  • Joining values into a string key without a separator makes [1,12] collide with [11,2].
  • The divisibility count restarts for every start index.

Reference solution

Python

from typing import List

def countDistinct(nums: List[int], k: int, p: int) -> int:
    children = [{}]
    ans = 0
    n = len(nums)
    for i in range(n):
        node = 0
        cnt = 0
        for j in range(i, n):
            v = nums[j]
            if v % p == 0:
                cnt += 1
            if cnt > k:
                break
            nxt = children[node].get(v)
            if nxt is None:
                nxt = len(children)
                children.append({})
                children[node][v] = nxt
                ans += 1
            node = nxt
    return ans

Java

public static int countDistinct(int[] nums, int k, int p) {
    Map<Integer, Integer> child = new HashMap<>();
    int nodes = 1, ans = 0;
    for (int i = 0; i < nums.length; i++) {
        int node = 0, cnt = 0;
        for (int j = i; j < nums.length; j++) {
            if (nums[j] % p == 0) cnt++;
            if (cnt > k) break;
            int key = node * 201 + nums[j];
            Integer nxt = child.get(key);
            if (nxt == null) {
                nxt = nodes++;
                child.put(key, nxt);
                ans++;
            }
            node = nxt;
        }
    }
    return ans;
}

C++

int countDistinct(vector<int>& nums, int k, int p) {
    unordered_map<long long, int> child;
    int nodes = 1, ans = 0, n = nums.size();
    for (int i = 0; i < n; i++) {
        int node = 0, cnt = 0;
        for (int j = i; j < n; j++) {
            if (nums[j] % p == 0) cnt++;
            if (cnt > k) break;
            long long key = (long long) node * 201 + nums[j];
            auto it = child.find(key);
            if (it == child.end()) {
                child[key] = nodes;
                node = nodes++;
                ans++;
            } else {
                node = it->second;
            }
        }
    }
    return ans;
}

JavaScript

var countDistinct = function(nums, k, p) {
    // the whole trie in one map: key node * 201 + value -> child id
    var child = new Map();
    var nodes = 1, ans = 0;
    for (var i = 0; i < nums.length; i++) {
        var node = 0, cnt = 0;
        for (var j = i; j < nums.length; j++) {
            if (nums[j] % p === 0) cnt++;
            if (cnt > k) break;
            var key = node * 201 + nums[j];
            var nxt = child.get(key);
            if (nxt === undefined) {
                nxt = nodes++;
                child.set(key, nxt);
                ans++;
            }
            node = nxt;
        }
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets