Leetcode 2261: K Divisible Elements Subarrays
You are given an integer array
nums and two integers k and p. Your task is to count the number of distinct subarrays where there are at most k elements divisible by p. A subarray is defined as a contiguous part of the array, and two subarrays are considered distinct if they differ in either length or at least one element.Problem
Approach
Steps
Complexity
Input: You are given an integer array `nums` and two integers `k` and `p`.
Example: nums = [5, 8, 3, 5, 6], k = 2, p = 5
Constraints:
• 1 <= nums.length <= 200
• 1 <= nums[i], p <= 200
• 1 <= k <= nums.length
Output: Return the number of distinct subarrays with at most `k` elements divisible by `p`.
Example: Output: 7
Constraints:
Goal: We need to find the distinct subarrays that satisfy the condition of having at most `k` elements divisible by `p`.
Steps:
• Iterate over the array to consider all possible subarrays.
• For each subarray, count the elements divisible by `p`.
• If the count is less than or equal to `k`, add the subarray to a set of distinct subarrays.
• Use hashing to ensure subarrays are distinct and avoid duplicates.
Goal: Ensure the solution works within the constraints for large input sizes.
Steps:
• The length of `nums` is between 1 and 200.
• The values in `nums` and `p` are between 1 and 200.
• The value of `k` is between 1 and the length of `nums`.
Assumptions:
• The input array `nums` is non-empty.
• Subarrays are considered distinct if they differ in length or in elements.
• Input: nums = [5, 8, 3, 5, 6], k = 2, p = 5
• Explanation: We can form the subarrays [5], [5,8], [5,8,3], [8], [8,3], [3], and [5,6], which all contain at most 2 elements divisible by 5. Hence, the output is 7.
• Input: nums = [10, 20, 30], k = 1, p = 10
• Explanation: The distinct subarrays satisfying the condition are [10], [20], [30], and [10,20], [20,30], and [10,20,30]. There are 6 distinct subarrays, and the output is 6.
Approach: We will iterate through all subarrays and keep track of the number of elements divisible by `p`. Using a set ensures that we count only distinct subarrays.
Observations:
• We need an efficient way to find all subarrays and check the number of divisible elements.
• Using hashing will help keep track of the distinct subarrays without manually comparing each one.
Steps:
• Start by iterating over all possible subarrays.
• For each subarray, count how many elements are divisible by `p`.
• If the count of divisible elements is less than or equal to `k`, add the subarray to a set.
• Ensure the set stores only distinct subarrays by using hashing.
Empty Inputs:
• The input array is non-empty, so there are no empty inputs.
Large Inputs:
• Ensure the solution handles input sizes up to 200 elements efficiently.
Special Values:
• Consider cases where all elements are divisible by `p`.
Constraints:
• Ensure the solution works within the problem's constraints, especially with larger values of `k`.
int countDistinct(vector<int>& nums, int k, int p) {
int res = 0, n = nums.size();
vector<int> cnt(201, 0); vector<long long> hash(201, 0);
for (int sz = 0; sz < n; sz++) {
unordered_set<int> s;
for(int i = 0; i + sz < n; i++){
cnt[i] += ((nums[i + sz] % p) == 0);
if(cnt[i] <= k) {
hash[i] = (hash[i] * 200 + nums[i + sz]) % 1000000007;
res += s.insert(hash[i]).second;
}
}
}
return res;
}
1 : Function Declaration
int countDistinct(vector<int>& nums, int k, int p) {
The function `countDistinct` takes three parameters: `nums` (a vector of integers), `k` (the maximum number of divisible elements), and `p` (the divisor used to check divisibility). It returns an integer representing the count of distinct subarrays that meet the given conditions.
2 : Size and Count Initialization
int res = 0, n = nums.size();
The variable `res` is initialized to zero to store the count of distinct subarrays, and `n` is the size of the `nums` array.
3 : Auxiliary Arrays
vector<int> cnt(201, 0); vector<long long> hash(201, 0);
Two vectors `cnt` and `hash` are initialized: `cnt` tracks how many elements in the subarray are divisible by `p`, and `hash` stores the hash value of each subarray for quick distinctness checking.
4 : Outer Loop (Subarray Size)
for (int sz = 0; sz < n; sz++) {
The outer loop iterates over all possible subarray sizes starting from each index in the `nums` array.
5 : Set Initialization
unordered_set<int> s;
A set `s` is initialized to store the unique hash values of the subarrays.
6 : Inner Loop (Subarray Elements)
for(int i = 0; i + sz < n; i++){
The inner loop generates the subarrays by starting at index `i` and extending the subarray by `sz` elements.
7 : Divisibility Count Update
cnt[i] += ((nums[i + sz] % p) == 0);
The `cnt` array is updated by checking if the element at index `i + sz` in `nums` is divisible by `p`. If it is, the count for that subarray index is incremented.
8 : Condition Check
if(cnt[i] <= k) {
This checks if the current subarray has at most `k` elements divisible by `p`. If true, it proceeds to the next steps.
9 : Hash Calculation
hash[i] = (hash[i] * 200 + nums[i + sz]) % 1000000007;
The hash value for the current subarray is updated by multiplying the existing hash by 200 and adding the current element `nums[i + sz]`, then taking the modulus to avoid overflow.
10 : Distinct Count Update
res += s.insert(hash[i]).second;
The `insert` function of the set `s` is used to add the subarray hash. If the hash is unique, it increments the `res` counter.
11 : Return Result
return res;
The function returns the count of distinct subarrays that satisfy the condition.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity is quadratic because we iterate over all subarrays and for each subarray, we check divisibility for each element.
Best Case: O(n^2)
Worst Case: O(n^2)
Description: The space complexity is O(n^2) due to the storage of distinct subarrays in a set.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus