Introduction

In this blog post, we will explore how to solve the LeetCode problem "974" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 * 104 -104 <= nums[i] <= 104 2 <= k <= 104

Explanation

Here's the solution to the problem:

• Prefix Sum and Modulo: Calculate the prefix sum of the array and take the modulo with k at each step. This helps identify subarrays with sums divisible by k.
• Frequency Count: Maintain a frequency count of the prefix sum modulo k values. If a modulo rem appears count times, it means there are count prefix sums that give the same remainder when divided by k. This indicates count * (count - 1) / 2 subarrays between those prefix sums that are divisible by k. Also, each prefix sum with a remainder of 0 represents a valid subarray.

• HashMap Optimization: Use a HashMap (or dictionary in Python) to efficiently store and retrieve the frequency of each prefix sum modulo k.

• Time Complexity: O(n), Space Complexity: O(k)

Code

    def subarraysDivByK(nums: list[int], k: int) -> int:
    """
    Given an integer array nums and an integer k, return the number of non-empty subarrays
    that have a sum divisible by k.

    Example:
    ----------
    nums = [4,5,0,-2,-3,1], k = 5 -> 7
    nums = [5], k = 9 -> 0
    """
    prefix_mod = 0
    mod_counts = {0: 1}  # Initialize with 0:1 to handle subarrays starting from index 0
    count = 0

    for num in nums:
        prefix_mod = (prefix_mod + num) % k
        if prefix_mod < 0:
            prefix_mod += k  # Handle negative remainders

        if prefix_mod in mod_counts:
            count += mod_counts[prefix_mod]
            mod_counts[prefix_mod] += 1
        else:
            mod_counts[prefix_mod] = 1

    return count