Daily Problem 10/03/2024: Make Sum Divisible by p

Find a maximal subarray of an integer array whose modulus by p is 0.

The full problem may be found on leetcode.

Analysis

The trivial solution is to look at every possible sub-array, which will have quadratic time complexity. This solution looks like

class SolutionTrivial:
    def minSubarray(self, nums: list[int], p: int) -> int:

        total = sum(nums)
        n = len(nums)
        total_remainder = total % p
        if total_remainder == 0:
            return 0

        best = n
        for k in range(n):
            s = 0
            for j in range(k, n):

                s += nums[j]
                if s % p == total_remainder and j + 1 - k < best:
                    best = j + 1 - k

        return best

and (obviously) exceeded the allowed runtime.

A better solution is to remember calculate the sums modulus and check if the complimenting modulus could be found. I got close, but I eventually confused myself into oblivion and decided to read the editorial.

Solution

The editorial presented a solution with linear time complexity. This solution used the ‘Two Sum’ memoization trick. I found a few optimizations that can be made:

• needed does not need to be (s - target + p) % p since the modulus is commutative,
• target can be computed just by taking the modulus of the sum.

In the end, this solution performed very well, beating \(89\%\) of submissions in its best run.

class Solution:
    def minSubarray(self, nums: list[int], p: int) -> int:
        total, n = sum(nums), len(nums)

        target = total % p
        if target == 0:
            return 0

        out = n
        mem = {0: -1}
        s = 0

        for k in range(n):

            s = (s + nums[k]) % p
            needed = (s - target) % p
            if needed in mem:
                out = min(out, k - mem[needed])

            mem[s] = k

        return -1 if out == n else out