Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.
Example 1:
Input: nums = [23,2,4,6,7], k = 6 Output: true Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6 Output: true Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42. 42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13 Output: false
Constraints:
1 <= nums.length <= 10^50 <= nums[i] <= 10^90 <= sum(nums[i]) <= 2^31 - 11 <= k <= 2^31 - 1
The description was taken from https://leetcode.com/problems/continuous-subarray-sum/.
#O(N) Time, O(K) Space where K is Number of Sums
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
if len(nums) < 2:
return False
if sum(nums) == 0:
return True seen = {}
curr_sum = 0
for i, num in enumerate(nums):
curr_sum += num
if curr_sum % k == 0 and curr_sum != num:
return True
if curr_sum % k not in seen:
seen[curr_sum % k] = i
elif i - seen[curr_sum % k] > 1:
return True
return FalseIn this question, we are looking for a subarray whose sum can be multiplied evenly into a specific value, k.
When we see a requirement like this, similar to problems like Pairs of Songs With Total Durations Divisible by 60, Subarray Sum Equals K, Path Sum III, and Four-Sum II, a prefix sum algorithm is a good approach.
A hint for using this algorithm is when we are given an input that requires us to find pairs or subarrays that sum, multiply, or divide to a given value.
First off, if the length of the input is less than two then we can return false because there is no way we could have a subarray of size two that would sum and divide evenly into k.
if len(nums) < 2:
return False
Also, if we have an array of at least two, and its sum is zero then we can return true because a sum of zero is always a multiple of k, according to the problem description.
if sum(nums) == 0:
return True
Next, we will create a HashMap for the sums that we have seen.
We will track each sum and its index so that we can tell later if we have a subarray of at least two indices.
seen = {}
We will also create a running sum counter.
curr_sum = 0
For each index and number in the input array, we will start by incrementing the current sum by its value.
for i, num in enumerate(nums):
curr_sum += num
If the current sum divides evenly by k, before returning true, we will first need to check that the current sum isn't the same as the current number.
If the current sum is the same as the number we are at, then that means we are just looking at the first value of the input array and that value divides evenly by k.
If both of these cases are true, then we will return true.
This would be the scenario where we have a valid consecutive subarray sum that begins at the beginning of the array.
if curr_sum % k == 0 and curr_sum != num:
return True
Otherwise, we will see if we have seen the remainder sum that we would need to add to the current sum so that it can be divided evenly by k.
If we haven't seen it, we will add the remainder of the current sum divided by k to the dictionary with the current index so that we may utilize it later if we come across its complement.
if curr_sum % k not in seen:
seen[curr_sum % k] = i
If it is already in the dictionary, then we will want to check if it is at least two indices behind.
We don't have any negative values in the input, so if we have a duplicate sum then that means that we have zeros padding the current subarray. If we have the same sum two indices back, then that means we have found two consecutive zeros that can be summed and divided evenly by k.
If this is the case, we will return true.
elif i - seen[curr_sum % k] > 1:
return True
If we never returned true, then we will return false because we weren't able to find a valid result.
return False