Jobs

Interviews

Discussions

Subarray Sums Divisible by K

Medium

Asked by:

39 views

Topics:

Arrays

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

Input: nums = [5], k = 9
Output: 0

Constraints:

1 <= nums.length <= 3 * 10⁴
-10⁴ <= nums[i] <= 10⁴
2 <= k <= 10⁴

Try coding it in LeetCode

Subarray Sums Divisible by K

Medium

Asked by:

39 views

Topics:

Arrays

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

Input: nums = [5], k = 9
Output: 0

Constraints:

1 <= nums.length <= 3 * 10⁴
-10⁴ <= nums[i] <= 10⁴
2 <= k <= 10⁴

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`?
Can the elements in the `nums` array be negative, positive, or zero?
What are the possible values for `k`? Can `k` be zero or negative?
If there are no subarrays whose sum is divisible by `k`, what should I return?
Are we looking for contiguous subarrays only, or can non-contiguous subarrays be considered?

Brute Force Solution

Approach

To solve this problem the brute force way, we'll check every possible group of numbers in the list. We'll calculate the sum of each group and see if that sum is evenly divisible by our target number.

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

First, pick a starting point in the list of numbers.
Then, create a group consisting of just that single number from your starting point.
Calculate the sum of the numbers in this group.
Check if the sum is divisible by the target number, and if it is, increase our counter.
Now, expand the group to include the next number in the list.
Calculate the sum of this larger group.
Check again if the sum is divisible by the target number, and if it is, increase our counter.
Keep expanding the group, one number at a time, calculating the sum and checking for divisibility with each expansion, until the group includes all the numbers from your starting point to the end of the list.
Now, go back to the beginning and choose the next number in the list as your new starting point.
Repeat the entire process of creating groups, calculating sums, and checking for divisibility, until you've used every number in the list as a starting point.
Finally, the counter will tell you how many groups of numbers have a sum that's divisible by the target number.

Code Implementation

def subarray_sums_divisible_by_k_brute_force(number_list, target):
    count_divisible_subarrays = 0

    for start_index in range(len(number_list)):
        current_subarray_sum = 0
        # Iterate through all subarrays starting
        # from the current start_index.
        for end_index in range(start_index, len(number_list)):
            current_subarray_sum += number_list[end_index]
            # Check divisibility after summing.
            if current_subarray_sum % target == 0:
                count_divisible_subarrays += 1

    return count_divisible_subarrays

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each element of the input array of size n as a starting point. For each starting element, it then iterates through the remaining elements to form subarrays. In the worst-case scenario, for each of the n starting points, it considers a subarray that potentially extends to the end of the array, requiring up to n operations. Thus, the total number of operations is proportional to n * n, giving a time complexity of O(n²).

Space Complexity

O(1) – The provided algorithm calculates the sum of each subarray on the fly using only a few variables. It iterates through subarrays, summing elements but it does not store the subarrays themselves or any intermediate sums in auxiliary data structures that scale with input size. The space used is therefore constant, regardless of the input array's size N. Thus, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The best way to solve this is to keep track of the remainders when you divide the running sums of the numbers by the given divisor. By using a clever shortcut with these remainders, you can quickly count the subarrays that add up to a multiple of the divisor without checking every single possibility.

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

Start by keeping track of how many times you've seen each possible remainder when dividing by the divisor. Initially, you've seen a remainder of 0 once (before you've looked at any numbers).
Go through the list of numbers one by one, and keep a running total of the sum so far.
For each number, find the remainder when you divide the running total by the divisor.
Check how many times you've seen that remainder before. The number of times you've seen it tells you how many earlier subarrays exist that, when combined with the current subarray, result in a total sum divisible by the divisor.
Add the number of times you've seen the remainder to a running count of good subarrays.
Update the count of how many times you've seen the current remainder.
Repeat until you've gone through all the numbers. The final count is the answer you're looking for.

Code Implementation

def subarray_sums_divisible_by_k(number_list, divisor):
    running_sum = 0
    subarray_count = 0
    remainder_counts = {0: 1}

    for number in number_list:
        running_sum += number
        remainder = running_sum % divisor
        
        # If negative, adjust remainder to be positive.
        if remainder < 0:
            remainder += divisor

        # Count subarrays that sum to a multiple of k.
        if remainder in remainder_counts:
            subarray_count += remainder_counts[remainder]

        # Update count of remainders.
        if remainder in remainder_counts:
            remainder_counts[remainder] += 1
        else:
            remainder_counts[remainder] = 1

    return subarray_count

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of n numbers once to calculate the running sum and remainder. Inside the loop, it performs a constant-time operation to update the count of remainders. Since the loop dominates the time complexity and each operation within the loop takes constant time, the overall time complexity is directly proportional to the input size n, resulting in O(n).

Space Complexity

O(K) – The algorithm uses a dictionary (or array) to store the counts of remainders modulo K. The size of this dictionary is determined by the possible remainders when dividing by K, which can range from 0 to K-1. Therefore, the space required to store the remainders is proportional to K, independent of the input array size N. The auxiliary space complexity is thus O(K).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0, as there are no subarrays in an empty array.
k is zero	Return 0, as division by zero is undefined and no sum can be divisible by 0 (unless the sum is also 0, which requires special handling).
Array with only one element	Check if the single element is divisible by k; return 1 if so, 0 otherwise.
Array with all elements equal to zero	The number of subarrays is n*(n+1)/2, where n is the array length, and return that as all subarray sums are 0, which is divisible by k for any non-zero k.
Array with all negative numbers	The prefix sum can become very negative, so use modulo operator carefully to handle negative remainders (add k until positive).
Large input array and large k value	The prefix sums should use long data type to avoid integer overflow.
k is a large number compared to elements in nums	Many remainders will likely be unique, so the HashMap can grow significantly, potentially impacting performance.
Integer overflow of sum within subarray	Use a long data type to store the running sum to avoid potential overflow issues.

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`?
Can the elements in the `nums` array be negative, positive, or zero?
What are the possible values for `k`? Can `k` be zero or negative?
If there are no subarrays whose sum is divisible by `k`, what should I return?
Are we looking for contiguous subarrays only, or can non-contiguous subarrays be considered?

Brute Force Solution

Approach

To solve this problem the brute force way, we'll check every possible group of numbers in the list. We'll calculate the sum of each group and see if that sum is evenly divisible by our target number.

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

First, pick a starting point in the list of numbers.
Then, create a group consisting of just that single number from your starting point.
Calculate the sum of the numbers in this group.
Check if the sum is divisible by the target number, and if it is, increase our counter.
Now, expand the group to include the next number in the list.
Calculate the sum of this larger group.
Check again if the sum is divisible by the target number, and if it is, increase our counter.
Keep expanding the group, one number at a time, calculating the sum and checking for divisibility with each expansion, until the group includes all the numbers from your starting point to the end of the list.
Now, go back to the beginning and choose the next number in the list as your new starting point.
Repeat the entire process of creating groups, calculating sums, and checking for divisibility, until you've used every number in the list as a starting point.
Finally, the counter will tell you how many groups of numbers have a sum that's divisible by the target number.

Code Implementation

def subarray_sums_divisible_by_k_brute_force(number_list, target):
    count_divisible_subarrays = 0

    for start_index in range(len(number_list)):
        current_subarray_sum = 0
        # Iterate through all subarrays starting
        # from the current start_index.
        for end_index in range(start_index, len(number_list)):
            current_subarray_sum += number_list[end_index]
            # Check divisibility after summing.
            if current_subarray_sum % target == 0:
                count_divisible_subarrays += 1

    return count_divisible_subarrays

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by keeping track of how many times you've seen each possible remainder when dividing by the divisor. Initially, you've seen a remainder of 0 once (before you've looked at any numbers).
Go through the list of numbers one by one, and keep a running total of the sum so far.
For each number, find the remainder when you divide the running total by the divisor.
Check how many times you've seen that remainder before. The number of times you've seen it tells you how many earlier subarrays exist that, when combined with the current subarray, result in a total sum divisible by the divisor.
Add the number of times you've seen the remainder to a running count of good subarrays.
Update the count of how many times you've seen the current remainder.
Repeat until you've gone through all the numbers. The final count is the answer you're looking for.

Code Implementation

def subarray_sums_divisible_by_k(number_list, divisor):
    running_sum = 0
    subarray_count = 0
    remainder_counts = {0: 1}

    for number in number_list:
        running_sum += number
        remainder = running_sum % divisor
        
        # If negative, adjust remainder to be positive.
        if remainder < 0:
            remainder += divisor

        # Count subarrays that sum to a multiple of k.
        if remainder in remainder_counts:
            subarray_count += remainder_counts[remainder]

        # Update count of remainders.
        if remainder in remainder_counts:
            remainder_counts[remainder] += 1
        else:
            remainder_counts[remainder] = 1

    return subarray_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0, as there are no subarrays in an empty array.
k is zero	Return 0, as division by zero is undefined and no sum can be divisible by 0 (unless the sum is also 0, which requires special handling).
Array with only one element	Check if the single element is divisible by k; return 1 if so, 0 otherwise.
Array with all elements equal to zero	The number of subarrays is n*(n+1)/2, where n is the array length, and return that as all subarray sums are 0, which is divisible by k for any non-zero k.
Array with all negative numbers	The prefix sum can become very negative, so use modulo operator carefully to handle negative remainders (add k until positive).
Large input array and large k value	The prefix sums should use long data type to avoid integer overflow.
k is a large number compared to elements in nums	Many remainders will likely be unique, so the HashMap can grow significantly, potentially impacting performance.
Integer overflow of sum within subarray	Use a long data type to store the running sum to avoid potential overflow issues.