2261. K Divisible Elements Subarrays LeetCode Solution
In this guide, you will get 2261. K Divisible Elements Subarrays LeetCode Solution with the best time and space complexity. The solution to K Divisible Elements Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of K Divisible Elements Subarrays
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.
Example 1:
Input: nums = [2,3,3,2,2], k = 2, p = 2
Output: 11
Explanation:
The elements at indices 0, 3, and 4 are divisible by p = 2.
The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are:
[2], [2,3], [2,3,3], [2,3,3,2], [3], [3,3], [3,3,2], [3,3,2,2], [3,2], [3,2,2], and [2,2].
Note that the subarrays [2] and [3] occur more than once in nums, but they should each be counted only once.
The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2.
Example 2:
Input: nums = [1,2,3,4], k = 4, p = 1
Output: 10
Explanation:
All element of nums are divisible by p = 1.
Also, every subarray of nums will have at most 4 elements that are divisible by 1.
Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.
1 <= nums.length <= 200
1 <= nums[i], p <= 200
1 <= k <= nums.length
Follow up:
Can you solve this problem in O(n2) time complexity?
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n^2)
2261. K Divisible Elements Subarrays LeetCode Solution in C++
struct TrieNode {
unordered_map<int, shared_ptr<TrieNode>> children;
int count = 0;
};
class Solution {
public:
int countDistinct(vector<int>& nums, int k, int p) {
int ans = 0;
for (int i = 0; i < nums.size(); ++i)
insert(root, nums, i, k, p, ans);
return ans;
}
private:
shared_ptr<TrieNode> root = make_shared<TrieNode>();
void insert(shared_ptr<TrieNode> node, const vector<int>& nums, int i, int k,
int p, int& ans) {
if (i == nums.size() || k - (nums[i] % p == 0) < 0)
return;
if (!node->children.contains(nums[i])) {
node->children[nums[i]] = make_shared<TrieNode>();
++ans;
}
insert(node->children[nums[i]], nums, i + 1, k - (nums[i] % p == 0), p,
ans);
}
}; /* code provided by PROGIEZ */
2261. K Divisible Elements Subarrays LeetCode Solution in Java
class TrieNode {
public Map<Integer, TrieNode> children = new HashMap<>();
public int count = 0;
}
class Solution {
public int countDistinct(int[] nums, int k, int p) {
for (int i = 0; i < nums.length; ++i)
insert(root, nums, i, k, p);
return ans;
}
private int ans = 0;
private TrieNode root = new TrieNode();
private void insert(TrieNode node, int[] nums, int i, int k, int p) {
if (i == nums.length || k - (nums[i] % p == 0 ? 1 : 0) < 0)
return;
if (!node.children.containsKey(nums[i])) {
node.children.put(nums[i], new TrieNode());
++ans;
}
insert(node.children.get(nums[i]), nums, i + 1, k - (nums[i] % p == 0 ? 1 : 0), p);
}
} // code provided by PROGIEZ
2261. K Divisible Elements Subarrays LeetCode Solution in Python
class TrieNode:
def __init__(self):
self.children: dict[int, TrieNode] = {}
self.count = 0
class Solution:
def countDistinct(self, nums: list[int], k: int, p: int) -> int:
ans = 0
root = TrieNode()
def insert(node: TrieNode, i: int, k: int):
nonlocal ans
if i == len(nums) or k - (nums[i] % p == 0) < 0:
return
if nums[i] not in node.children:
node.children[nums[i]] = TrieNode()
ans += 1
insert(node.children[nums[i]], i + 1, k - (nums[i] % p == 0))
for i in range(len(nums)):
insert(root, i, k)
return ans # code by PROGIEZ
