algoadvance

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 sum is a multiple of 6.

Example 2:

Input: nums = [23, 2, 6, 4, 7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an entire array whose sum is a multiple of 6.

Example 3:

Input: nums = [23, 2, 6, 4, 7], k = 13
Output: false

Clarifying Questions

1. What is the size of the input array nums?
   • Typical constraint details.
2. Can the input array include negative numbers?
   • Relevant for sum calculations.
3. What if k is zero?
   • Special handling might be needed.

Strategy

1. Zero Special Case: If k is zero, find if there exists a zero-sum subarray of size ≥ 2.
2. Prefix Sum and Remainder Method: Use prefix sums and a hashmap to store remainders.
   • Maintain a cumulative sum and a hashmap to store the remainder of the cumulative sum when divided by k.
   • If the same remainder appears again and the subarray is of length ≥ 2, it implies the subarray sum is a multiple of k.

Code

def checkSubarraySum(nums, k):
    if k == 0:
        # Special case handling for k = 0
        for i in range(len(nums) - 1):
            if nums[i] == 0 and nums[i + 1] == 0:
                return True
        return False
    
    remainder_map = {0: -1}  # Handle if a subarray from the start
    cumulative_sum = 0
    
    for i in range(len(nums)):
        cumulative_sum += nums[i]
        
        if k != 0:
            cumulative_sum %= k
        
        if cumulative_sum in remainder_map:
            if i - remainder_map[cumulative_sum] > 1:  # At least 2 elements
                return True
        else:
            remainder_map[cumulative_sum] = i
            
    return False

Time Complexity

• Time Complexity: O(n), where n is the length of the array nums. We only traverse the array once.
• Space Complexity: O(min(n, k)), as we are storing the remainders in a hashmap. At most, we might need to store min(n, k) entries if all remainders are unique.

This algorithm efficiently checks for the presence of a continuous subarray whose sum is a multiple of k, while maintaining linear time complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?