Problem Description

You are given a list of non-negative numbers and a target integer k. The task is to check if this list contains a continuous subarray of at least two numbers that sums up to a multiple of k.

Inputs:

1. A list of non-negative numbers.
2. An integer k.

Output:

Return true if there exists a continuous subarray of size at least 2 that adds up to n*k (n is an integer). Otherwise, return false.

Example:

Let's consider an example for better understanding.

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

Firstly, there is a subarray [2, 4] whose sum is 6, which is 1*6. So, the function should return True in this case.

Approach

The key is to use a Hashtable called prefixToIndex to keep a running sum prefix. If we find the prefix already in the Hashtable and the distance between its index and current index is greater than or equal to 2, then we find such subarray, return true immediately.

Because we are looking for multiples of k, the sum of running numbers prefix can be large. To reduce it, we take the modulo of k, if k is not 0. Using this prefix sum approach we save our computations.

We iterate through nums, and for every element:

• add it to prefix
• if k != 0, prefix %= k
• check if prefix is present in prefixToIndex
  • If it is present and diff of its index and current index >= 2, return True
  • If it is not present, add it to prefixToIndex

At the end of the iteration, we could not find a suitable subarray, return False.

By iterating through the list only once, the time complexity is O(n).

Python Solution

1
2python
3class Solution:
4    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
5        prefix = 0
6        prefixToIndex = {0: -1}
7        
8        for i, num in enumerate(nums):
9            prefix += num
10            if k != 0:
11                prefix %= k
12            if prefix in prefixToIndex and i - prefixToIndex[prefix] > 1:
13                return True
14            if prefix not in prefixToIndex:
15                prefixToIndex[prefix] = i
16            
17        return False

Java Solution

1
2java
3class Solution {
4    public boolean checkSubarraySum(int[] nums, int k) {
5        int prefix = 0;
6        Map<Integer, Integer> prefixToIndex = new HashMap<>();
7        prefixToIndex.put(0, -1);
8        
9        for(int i=0; i<nums.length; i++){
10            prefix += nums[i];
11            if(k != 0) prefix %= k;
12            if(prefixToIndex.containsKey(prefix)){
13                if(i - prefixToIndex.get(prefix) > 1) return true;
14            }else{
15                prefixToIndex.put(prefix, i);
16            }
17        }
18        
19        return false;
20    }  
21}

Javascript Solution

1
2javascript
3var checkSubarraySum = function(nums, k) {
4    let prefix = 0;
5    let prefixToIndex = {0:-1};
6    
7    for(let i=0; i<nums.length; i++){
8        prefix += nums[i];
9        if(k !== 0) prefix %= k;
10        if(prefixToIndex[prefix] !== undefined){
11            if(i - prefixToIndex[prefix] > 1) return true;
12        }else{
13            prefixToIndex[prefix] = i;
14        }
15    }
16    
17    return false;
18};

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool checkSubarraySum(vector<int>& nums, int k) {
6        int prefix = 0;
7        unordered_map<int, int> prefixToIndex{{0, -1}};
8        
9        for(int i=0; i<nums.size(); i++){
10            prefix += nums[i];
11            if(k != 0) prefix %= k;
12            if(prefixToIndex.count(prefix)){
13                if(i - prefixToIndex[prefix] > 1) return true;
14            }else{
15                prefixToIndex[prefix] = i;
16            }
17        }
18        
19        return false;
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public bool CheckSubarraySum(int[] nums, int k) {
5        int prefix = 0;
6        Dictionary<int, int> prefixToIndex = new Dictionary<int, int>();
7        prefixToIndex[0] = -1;
8        
9        for(int i=0; i<nums.Length; i++){
10            prefix += nums[i];
11            if(k != 0) prefix %= k;
12            if(prefixToIndex.ContainsKey(prefix)){
13                if(i - prefixToIndex[prefix] > 1) return true;
14            }else{
15                prefixToIndex[prefix] = i;
16            }
17        }
18        
19        return false;
20    }
21}

You can also explain with the test case with inputs [23, 2, 6, 4, 7] and k=6, it works in the same way but the subarray includes all the numbers and the sum is 42 or 7*6.All these solutions explore every possible combination of subarrays by using prefix sums. They add each new number to the prefix sum, and store these sums in a Hashtable. By also keeping the index of each sum, these solutions can check if a matching sum is found later in the array. If a matching sum is found with an index at least 2 greater, that means it has found a subarray that adds up to a multiple of k. Also, by taking the modulo of each prefix sum (if k is not zero), these solutions prevent the numbers from getting too large and also find the necessary subarrays even when the multiple of k is not exactly k.

Wrapping up, these solutions are effective in finding continuous subarrays that sum up to a multiple of k. They are efficient with a time complexity of O(n), as they employ prefix sums to avoid repetitive computation, and use a Hashtable for constant-time access to past sums.

If you are undertaking a series of such problems, understanding the underlying strategy of prefix sums could help decipher and create solutions quicker. Hence, mastering this common algorithmic strategy could be greatly beneficial to tackle array-based problems in coding interviews. Besides, understanding the hashtable concept will provide a valuable foundation for more complex problems. The application domains for this problem can range from software development, data analysis to machine learning, depending on the nature of the task at hand.

Remember, practicing and understanding these problems would make a significant difference in enhancing your problem-solving skills, necessary for the competitive programming world. Don't hesitate to tackle difficult problems, as they are the ones that effectuate growth and learning. It's your journey to take, so embark on it with confidence and exhilaration.