We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

K Divisible Elements Subarrays

Number: 2339

Difficulty: Medium

Paid? No

Companies: Amazon, Uber

Problem Description

Given an integer array nums and two integers k and p, count the number of distinct subarrays (contiguous non-empty sequences) that have at most k elements divisible by p. Two subarrays are considered distinct if they differ in length or at least one element at any index.

Key Insights

  • Iterate using two nested loops to generate all possible subarrays.
  • Maintain a counter for elements divisible by p; break if the count exceeds k.
  • Use a set to capture unique subarrays, ensuring duplicates are ignored.
  • Subarrays can be serialized using tuples, strings, or any immutable structure to efficiently check for uniqueness.
  • Although a brute force approach is O(n^3) in the worst case due to subarray serialization, the constraints (nums length up to 200) allow this approach.

Space and Time Complexity

Time Complexity: O(n^2 * m), where n is the length of the array and m is the cost of serializing each subarray.
Space Complexity: O(n^2 * m) for storing the serialized subarrays in the worst case.

Solution

We generate subarrays using nested loops. For each starting index, extend the subarray one element at a time while counting the number of divisible elements. If the count exceeds k, we stop expanding that subarray. Each valid subarray is then converted into a string or tuple and inserted into a set to ensure uniqueness. Finally, we return the size of the set which represents the number of distinct valid subarrays.

Code Solutions

# Python solution using nested loops and a set to store unique subarrays.
def countDistinct(nums, k, p):
    distinct_subarrays = set()  # set to store unique subarray representations
    n = len(nums)
    for i in range(n):
        count = 0  # count for elements divisible by p
        current_subarray = []
        for j in range(i, n):
            current_subarray.append(nums[j])
            if nums[j] % p == 0:
                count += 1
            if count > k:
                break
            # Convert list to tuple (hashable) and add to the set
            distinct_subarrays.add(tuple(current_subarray))
    return len(distinct_subarrays)

# Example usage:
nums = [2, 3, 3, 2, 2]
k = 2
p = 2
print(countDistinct(nums, k, p))  # Expected output: 11
← Back to All Questions