Practice/Meta/Leetcode 523. Continuous Subarray Sum

Leetcode 523. Continuous Subarray Sum

CodingMust

Problem

Given an integer array nums and an integer k, determine if there exists a contiguous subarray of length at least 2 whose elements sum to a multiple of k. Return true if such a subarray exists, otherwise return false.

A multiple of k is any number that can be expressed as k * n where n is an integer. Note that 0 is always considered a multiple of k.

Requirements

1. The subarray must be contiguous (elements must be adjacent in the original array)
2. The subarray must have length of at least 2 elements
3. The sum of the subarray elements must be divisible by k (i.e., sum % k == 0)
4. Return true if at least one such subarray exists, false otherwise

Constraints

• 1 ≤ nums.length ≤ 105
• 0 ≤ nums[i] ≤ 109
• 1 ≤ k ≤ 231 - 1
• Expected time complexity: O(n)
• Expected space complexity: O(min(n, k))

Examples

Example 1:

Input: nums = [23, 2, 4, 6, 7], k = 6 Output: true Explanation: The subarray [2, 4] has sum 6, which is divisible by 6.

Example 2:

Input: nums = [23, 2, 6, 4, 7], k = 13 Output: true Explanation: The subarray [23, 2, 6, 4, 7] has sum 42, which is divisible by 13.

Example 3:

Input: nums = [23, 2, 4, 6, 7], k = 13 Output: false Explanation: No contiguous subarray of length ≥ 2 has a sum divisible by 13.

Example 4:

Input: nums = [5, 0, 0, 0], k = 3 Output: true Explanation: The subarray [0, 0] has sum 0, which is divisible by 3.