# Continuous Subarray Sum LeetCode Solution

Difficulty Level Medium
Array Difficulty : Medium Hashing Math tiktok Walmart Global techViews 2769

## Problem Statement

Continuous Subarray Sum LeetCode Solution – Given an integer array `nums` and an integer `k`, return `true` if `nums` has a continuous subarray of the size of 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`5m
• `0 <= nums[i] <= 10`9
• `0 <= sum(nums[i]) <= 2`31` - 1`
• `1 <= k <= 2`31` - 1`

## Approach

### Idea:

1. this problem is the same as Subarray sum equals K with some modification
2. We need a subarray say from i to j such that sum of all elements is divisible by k.
3. We make a prefix sum array where prefixSum[i] is the (sum of first i elements)%k.
4. for some prefixSum(0,j) , we need to check if there exist some prefixSum(0,i) such that both are equal.
5. if they both are equal then it means the subarray i+1 to j has sum==0 so this subarray is divided by k

## Code:

### Continuous Subarray Sum C++ Leetcode Solution:

```class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {

int n=nums.size();

vector<int> arr(n,0);

arr=nums%k;

unordered_map<int,int> mp;

mp.insert({arr,0});

for(int i=1;i<n;i++)
{
arr[i]=nums[i]+arr[i-1];
arr[i]=arr[i]%k;

if(arr[i]==0)return true;

if(mp.find(arr[i])!=mp.end()){

int idx=mp[arr[i]];

if(i-idx==1)continue;

return true;
}

mp[arr[i]]=i;
}

return false;
}
};```

### Continuous Subarray Sum Java Leetcode Solution:

```class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>(){{put(0,-1);}};;
int runningSum = 0;
for (int i=0;i<nums.length;i++) {
runningSum += nums[i];
if (k != 0) runningSum %= k;
Integer prev = map.get(runningSum);
if (prev != null) {
if (i - prev > 1) return true;
}
else map.put(runningSum, i);
}
return false;
}
}```

## Complexity Analysis :

### Time Complexity:

The Time Complexity of the above solution is O(n) where n = the size of the input array since we traversed the entire array once.

### Space Complexity:

The Space Complexity of the above solution is O(n) for prefix sum and O(k) for hashmap.

Translate »