Question of the week 11.20

Coding keep your coding sharp
1

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.

Leet code 974

Please post your solutions here!

2 
   The version of this based on reminders (https://leetcode.com/problems/subarray-sums-divisible-by-k/) is similar, but has a caveat that relates to how the .net mod operator works with negative numbers - see https://stackoverflow.com/questions/1082917/mod-of-negative-number-is-melting-my-brain. 
See you next week ! Regards,

Sandesh

Solution -
-------------
public class Solution {
    public int SubarraysDivByK(int[] nums, int k) {
        
        Dictionary<int,int> lookup = new Dictionary<int,int>();
        int sum=0, cnt=0;
        
        foreach (int n in nums)
        {
            lookup[Modulo(sum, k)] = lookup.ContainsKey(Modulo(sum, k)) ? lookup[Modulo(sum, k)]+1 : 1;
            sum += n;
            if (lookup.ContainsKey(Modulo(sum, k))) cnt += lookup[Modulo(sum, k)];
        }
        return cnt;
    }
    
    private int Modulo(int dividend, int divisor)
    {
        int rawmod = dividend % divisor;
        return rawmod < 0 ? divisor + rawmod : rawmod;
    }
}
---------------
3

Too many calls to Modulo. You can do this also.

public int SubarraysDivByK(int[] nums, int k) {
    var remainderCounts = new Dictionary<int, int>();
    remainderCounts[0] = 1;
    
    var remainder = 0;
    var resultCount = 0;
    int sum = 0;
    
    foreach (int n in nums) {
        sum += n;
        
        remainder = sum % k;
        if (remainder < 0) {
            // By default, C# returns the negative remainder
            remainder += k;
        }
        
        if (!remainderCounts.ContainsKey(remainder)) {
            remainderCounts[remainder] = 0;
        }

        resultCount += remainderCounts[remainder];
        remainderCounts[remainder]++;
    }
    
    return resultCount;
}
1 Like