974. Subarray Sums Divisible by K

링크 - https://leetcode.com/problems/subarray-sums-divisible-by-k/description/?envType=company&envId=tiktok&favoriteSlug=tiktok-thirty-days

난이도 - Medium

Intuition

우리는 따로 k길이를 갖는 list를 사용하여 이 문제를 풀 수 있다. 우리는 modulo를 사용하여 항상 0 - k-1값을 가지는 개수를 알 수 있으므로 nums를 for문으로 지나가며 생기는 modulo값을 list에 더해가며 문제를 풀 수 있다.

Code

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix_mod = 0

        # There are k mod groups 0, ..., k-1
        mods = [0] * k
        mods[0] = 1

        ans = 0
        for num in nums:
            # Take modulo twice to avoid negative remainders
            prefix_mod = (prefix_mod + num % k + k) % k
            # Add the count of subarrays that have the same remainder as the current one to cancle out the remainders
            ans += mods[prefix_mod]
            mods[prefix_mod] += 1

        return ans

Complexity

Time Complexity: O(n + k)

Space Complexity: O(k)