maw.sh > Mahmoud Ashraf Website

SupportPalestine

974. Subarray Sums Divisible by K 🔗

Date: Jun 09, 2024

Tags: prefix-sum

Description

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

Optimal

function subarraysDivByK(nums: number[], k: number): number {
  let result = 0;
  let prefix = 0;
  const hash: Record<number, number> = { 0: 1 };

  for (const x of nums) {
    prefix += x;
    const r = ((prefix % k) + k) % k;

    const y = hash[r] ?? 0;
    result += y;
    hash[r] = y + 1;
  }

  return result;
}

export { subarraysDivByK };

Brute-force

function subarraysDivByK(nums: number[], k: number): number {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    let current = 0;
    for (let j = i; j < nums.length; j++) {
      current += nums[j];
      if (current % k === 0) count++;
    }
  }

  return count;
}

export { subarraysDivByK };