974. Subarray Sums Divisible by K

leetcode medium

#array#backtracking#csharp#leetcode#medium#prefix-sum

Task

Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k.

Подмассив — это непрерывная часть массива.

Пример:

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]

C# solution

matched/original

public class Solution {
    public int SubarraysDivByK(int[] nums, int k) {
        int prefixMod = 0, result = 0;
        int[] modGroups = new int[k];
        modGroups[0] = 1;
        foreach (int num in nums) {
            prefixMod = (prefixMod + num % k + k) % k;
            result += modGroups[prefixMod];
            modGroups[prefixMod]++;
        }
        return result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SubarraysDivByK(vector<int>& nums, int k) {
        int prefixMod = 0, result = 0;
        vector<int>& modGroups = new int[k];
        modGroups[0] = 1;
        foreach (int num in nums) {
            prefixMod = (prefixMod + num % k + k) % k;
            result += modGroups[prefixMod];
            modGroups[prefixMod]++;
        }
        return result;
    }
}

Java solution

matched/original

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int prefixMod = 0, result = 0;
        int[] modGroups = new int[k];
        modGroups[0] = 1;

        for (int num : nums) {
            prefixMod = (prefixMod + num % k + k) % k;
            result += modGroups[prefixMod];
            modGroups[prefixMod]++;
        }

        return result;
    }
}

JavaScript solution

matched/original

var subarraysDivByK = function(nums, k) {
    let prefixMod = 0, result = 0;
    const modGroups = new Array(k).fill(0);
    modGroups[0] = 1;

    for (let num of nums) {
        prefixMod = (prefixMod + num % k + k) % k;
        result += modGroups[prefixMod];
        modGroups[prefixMod]++;
    }

    return result;
};

Python solution

matched/original

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        prefixMod = 0
        result = 0
        modGroups = [0] * k
        modGroups[0] = 1

        for num in nums:
            prefixMod = (prefixMod + num % k + k) % k
            result += modGroups[prefixMod]
            modGroups[prefixMod] += 1

        return result

Go solution

matched/original

func subarraysDivByK(nums []int, k int) int {
    prefixMod, result := 0, 0
    modGroups := make([]int, k)
    modGroups[0] = 1

    for _, num := range nums {
        prefixMod = (prefixMod + num % k + k) % k
        result += modGroups[prefixMod]
        modGroups[prefixMod]++
    }

    return result
}

Explanation

Algorithm

Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1.

Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений.

Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k.

😎