[Prefix Sum] Continuous Subarray Sum

[sudosf]

Problem

Given an integer array and k, return true if there is a subarray of length at least 2 whose sum is a multiple of k.

References

• LeetCode: https://leetcode.com/problems/continuous-subarray-sum/
• GFG: https://www.geeksforgeeks.org/problems/largest-subarray-with-0-sum/1
• Sheet: https://www.risingbrain.org/sheet#array (Prefix Sum [Two Pointer] Two Sum II - Input Array Is Sorted #5)
• Parent: Pattern: Prefix Sum (Arrays) #51

Difficulty

🟡 Medium

Companies

Facebook, DE Shaw, Sumo Logic

Notes

Language: Java
Store prefix sum mod k in a map. If the same remainder appears again with at least 2 elements between, you have a valid subarray.