K Divisible Elements Subarrays

Medium

Asked by:

18 views

Topics:

Arrays

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.

Constraints:

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

Follow up:

Can you solve this problem in O(n²) time complexity?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the input array `nums` and the values within it? Specifically, what are the maximum and minimum possible values for `n` (the length of `nums`), and for each `nums[i]`?
What are the constraints on `k` and `p`? Specifically, what are the maximum and minimum possible values for each?
If no subarrays satisfy the condition (having at most `k` elements where `nums[i] % p == 0`), what should the function return? Should I return an empty list, a special value like `null`, or something else?
Are overlapping subarrays considered distinct? For example, if `nums` is `[2,2,2]` with `k=2`, `p=2`, should `[2,2]` (appearing twice) and `[2]` (appearing three times) be counted as distinct subarrays, or should each unique subarray be counted only once?
Is the order of elements within each subarray important for determining if the subarray is distinct? In other words, are `[1,2]` and `[2,1]` considered the same subarray?

Brute Force Solution

Approach

The brute force approach to finding K-divisible element subarrays involves checking every possible subarray within the given sequence. We'll examine each subarray to see if it meets the K-divisibility criteria, and then count only the unique subarrays that satisfy it.

Here's how the algorithm would work step-by-step:

Consider every possible starting position for a subarray in the sequence.
For each starting position, consider every possible ending position, thus defining a subarray.
For each generated subarray, count how many elements are divisible by a specific number, let's call it 'K'.
If the count of divisible elements is not greater than another specific number, also called 'K', then add that subarray to a collection of valid subarrays.
Since identical subarrays might be generated multiple times, make sure to count only the unique subarrays from the collection.
Finally, report the total number of unique, valid subarrays found.

Code Implementation

def k_divisible_elements_subarrays_brute_force(numbers, k_divisor, max_divisible_count):
    number_of_elements = len(numbers)
    valid_subarrays = set()

    # Iterate through all possible start indices
    for start_index in range(number_of_elements):

        # Iterate through all possible end indices for each start index
        for end_index in range(start_index, number_of_elements):
            divisible_count = 0

            # Count divisible elements in the current subarray
            for index in range(start_index, end_index + 1):
                if numbers[index] % k_divisor == 0:
                    divisible_count += 1

            # This check ensures we only keep subarrays that meet the divisibility criteria
            if divisible_count <= max_divisible_count:
                subarray = tuple(numbers[start_index:end_index + 1])

                # Add the subarray to the set to ensure uniqueness
                valid_subarrays.add(subarray)

    return len(valid_subarrays)

Big(O) Analysis

Time Complexity

O(n³) – The algorithm iterates through all possible subarrays. There are n possible starting positions. For each starting position, there are n possible ending positions, resulting in nested loops that contribute O(n²). For each subarray, we iterate through it to count the number of elements divisible by K, taking O(n) time in the worst case (when the subarray spans almost the whole initial array). Because we are checking if elements are divisible within each of these subarrays, the time complexity becomes O(n³) because of the nested loops and the internal divisibility check on each subarray. The check for uniqueness might add to the constant factor, but does not change the Big O notation.

Space Complexity

O(N^2) – The brute force approach, as described, stores valid subarrays in a collection to ensure uniqueness. In the worst-case scenario, where almost all subarrays meet the K-divisibility criteria, this collection could potentially store all possible subarrays of the input sequence. Since there can be O(N^2) subarrays in an array of size N, the space required to store these subarrays will be proportional to N^2. Therefore, the space complexity is O(N^2).

Optimal Solution

Approach

The goal is to find all the unique groups of numbers within a larger list, with the rule that each group can only have a limited number of numbers that are far away from a target value. We'll efficiently find these groups by checking and comparing numbers as we go along, making sure not to count the same group twice.

Here's how the algorithm would work step-by-step:

Go through each number in the list one by one.
For each number, consider it as the starting point of a possible group.
From that starting point, expand the group by adding more numbers from the list, one at a time.
As you add numbers to the group, keep track of how many of those numbers are different from the target value.
If the count of different numbers exceeds the allowed limit, stop expanding the group.
Once you've created a group, check if this exact group (with the same numbers in the same order) has already been counted.
If it's a new unique group, add it to your count of unique groups.
Continue this process until you've considered every number in the list as a potential starting point, and built all possible groups.

Code Implementation

def k_divisible_elements_subarrays(nums, k_limit, target_value):
    unique_subarrays_count = 0
    seen_subarrays = set()

    for start_index in range(len(nums)):
        for end_index in range(start_index, len(nums)):
            current_subarray = tuple(nums[start_index:end_index + 1])
            
            different_elements_count = 0
            for element in current_subarray:
                if element % target_value != 0:
                    different_elements_count += 1

            # Only process subarrays within the k_limit constraint
            if different_elements_count <= k_limit:

                # Prevents duplicate counting of same subarrays
                if current_subarray not in seen_subarrays:
                    unique_subarrays_count += 1
                    seen_subarrays.add(current_subarray)

    return unique_subarrays_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each element of the input array of size n as a potential starting point for a subarray. For each starting element, it expands the subarray by including subsequent elements until the 'k divisible elements' constraint is violated or the end of the array is reached. The maximum length of the inner loop (subarray expansion) is also proportional to n. Thus, we have nested loops where the outer loop iterates n times, and in the worst case, the inner loop also iterates up to n times, giving us a time complexity of approximately n * n. Therefore, the overall time complexity is O(n²).

Space Complexity

O(N^2) – The algorithm constructs subarrays, and to efficiently check for duplicates, it implicitly uses a set or similar data structure to store the subarrays encountered so far. In the worst case, where many or all subarrays are unique, the number of these subarrays could be proportional to N^2, as each element could potentially start a subarray and extend up to N elements. Thus, the auxiliary space used to store these unique subarrays can grow quadratically with the input size N. Therefore, the space complexity is O(N^2).

Edge Cases

Case	How to Handle
Empty input array	Return 0 as there are no subarrays.
k is zero	Every subarray will be divisible by 0 which leads to ArithmeticException so throw IllegalArgumentException.
nums array contains only identical elements, and k divides that element	The number of unique subarrays will scale linearly with the size of the input array; (n*(n+1))/2.
Large array with many elements divisible by k	Ensure the solution's time complexity is efficient (e.g., O(n^2) or better).
Integer overflow when calculating the number of divisible elements	Use appropriate data types (e.g., long) to prevent integer overflow.
k is a large number, larger than the max element in nums	Handle the case by counting only subarrays where at least one element matches with k.
Array contains very large numbers (close to Integer.MAX_VALUE)	Check the element by element divisibility and handle possible integer overflow during divisibility check.
No subarray fulfills the criteria	The solution correctly returns 0 if no such subarray exists without causing errors.

Empty input array

How to Handle:

Return 0 as there are no subarrays.

k is zero

How to Handle:

Every subarray will be divisible by 0 which leads to ArithmeticException so throw IllegalArgumentException.

nums array contains only identical elements, and k divides that element

How to Handle:

The number of unique subarrays will scale linearly with the size of the input array; (n*(n+1))/2.

Large array with many elements divisible by k

How to Handle:

Ensure the solution's time complexity is efficient (e.g., O(n^2) or better).

Integer overflow when calculating the number of divisible elements

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow.

k is a large number, larger than the max element in nums

How to Handle:

Handle the case by counting only subarrays where at least one element matches with k.

Array contains very large numbers (close to Integer.MAX_VALUE)

How to Handle:

Check the element by element divisibility and handle possible integer overflow during divisibility check.

No subarray fulfills the criteria

How to Handle:

The solution correctly returns 0 if no such subarray exists without causing errors.