Continuous Subarray Sum

class Solution {
public:
    bool hasSubarrayWithSum(vector<int>& arr, int divisor) {
        int cumulativeSumModulo = 0;
        unordered_map<int, int> moduloIndexMap;
        moduloIndexMap[0] = -1;

        for (int idx = 0; idx < arr.size(); idx++) {
            cumulativeSumModulo = (cumulativeSumModulo + arr[idx]) % divisor;

            if (moduloIndexMap.find(cumulativeSumModulo) != moduloIndexMap.end()) {
                if (idx - moduloIndexMap[cumulativeSumModulo] > 1) {
                    return true;
                }
            } else {
                moduloIndexMap[cumulativeSumModulo] = idx;
            }
        }

        return false;
    }
};

This solution tackles the problem of finding a continuous subarray within an array that sums to a multiple of a given number (divisor). The implementation is in C++ and uses a combination of a cumulative sum approach and hashing to efficiently solve the problem.

• The function hasSubarrayWithSum accepts a vector arr and an integer divisor as parameters.
• It initializes cumulativeSumModulo to keep track of the cumulative sum modulo divisor, and an unordered_map<int, int> called moduloIndexMap to store the first occurrence index of each modulo value.
• moduloIndexMap is initialized with the key 0 set to -1 to handle the edge case where a valid subarray begins from index 0.
• A for loop iterates through each element in the array:
  • The cumulativeSumModulo is updated by adding the current array element (arr[idx]) and taking modulo divisor.
  • If the current cumulativeSumModulo exists in moduloIndexMap, it checks if the subarray length is greater than 1 (as a valid subarray must contain at least two elements).
    • If so, the function returns true, indicating that a qualifying subarray has been found.
  • If the cumulativeSumModulo is not found in moduloIndexMap, the current index is added to the map with cumulativeSumModulo as the key.
• If the loop completes without finding any such subarray, the function returns false.

This solution efficiently checks subarrays by leveraging the properties of cumulative sums and the modulo operation, combined with map lookups to avoid redundant calculations. This approach significantly reduces complexity, especially compared to a naive method involving nested loops.

import java.util.HashMap;

class Solution {

    public boolean hasSubarraySum(int[] elements, int divisor) {
        int cumulativeSumMod = 0;
        HashMap<Integer, Integer> modIndexMap = new HashMap<>();
        modIndexMap.put(0, -1);

        for (int index = 0; index < elements.length; index++) {
            cumulativeSumMod = (cumulativeSumMod + elements[index]) % divisor;

            if (modIndexMap.containsKey(cumulativeSumMod)) {
                // checks subarray size is greater than 1
                if (index - modIndexMap.get(cumulativeSumMod) > 1) {
                    return true;
                }
            } else {
                // record the current index for this mod result
                modIndexMap.put(cumulativeSumMod, index);
            }
        }

        return false;
    }
}

The provided Java solution addresses the problem of determining whether a continuous subarray of given elements, whose sum is divisible by a specified divisor, exists within a given array of integers. The solution leverages a HashMap to store modulo results derived from the cumulative sum of elements processed sequentially.

• Initially, insert a key-value pair (0, -1) into the HashMap, allowing straightforward validation for cases where an early subarray sum is exactly divisible by the divisor.

• Iterate through the elements, computing a running cumulative sum modulated by the divisor to maintain results within the necessary range and store or verify these results:

  1. For each element, update the cumulative sum, modulo by the divisor.
  2. Check the HashMap to see whether the same remainder has been encountered previously:
     • If yes, ensure that the subarray formed between the current and previously stored index is of size greater than one (i.e., the difference between indices is more than one). If this holds true, the function immediately returns true.
     • If no match is found for the remainder, store the current index mapped to the current remainder in the HashMap.

• The function returns false if no qualifying subarray is found by the end of the iteration through the elements.

The solution is efficient due to its use of a HashMap, allowing constant time complexity operations for adding and checking entries, while overall processing of the elements is linear in time complexity relative to the array size. This method provides a powerful way to deal with cumulative sums modulated by a divisor in array analysis problems.

class Solution:
    def hasSubarrayWithSum(self, values, divisor):
        current_modulo = 0
        encountered_modulo = {0: -1}

        for idx in range(len(values)):
            current_modulo = (current_modulo + values[idx]) % divisor

            if current_modulo in encountered_modulo:
                if idx - encountered_modulo[current_modulo] > 1:
                    return True
            else:
                encountered_modulo[current_modulo] = idx

        return False

The provided Python code defines a method, hasSubarrayWithSum, which checks if there exists a continuous subarray within a given list, values, whose sum is divisible by another input, divisor. This method belongs to the Solution class.

Here's a step-by-step walkthrough of how the method functions:

1. Initialize current_modulo to zero - This variable tracks the cumulative sum's remainder when divided by the divisor.
2. Create a dictionary, encountered_modulo, to store the remainders and their corresponding indices. It starts with the remainder 0 at index -1.
3. Iterate through the list using the index. For each element:
   • Calculate the new current_modulo as the sum of the current current_modulo and the current value from the list, then take this sum modulo the divisor.
   • Check if current_modulo has been encountered before:
     • If it has, and if the difference between the current index and the stored index of current_modulo is greater than 1, return True.
   • If current_modulo has not been encountered before, update encountered_modulo with the current index.
4. After completing the loop, if no such subarray is found, return False.

This approach uses a hashmap to optimize checking for previously encountered remainders, ensuring that the function efficiently determines if the desired subarray exists.