Subarray Sum length at least two, that's are multiple of K

Problem:

Given an integer array nums and an integer k, return true if nums have 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 y such that x = y * k.0 is always a multiple of k

Example, nums = [9, 5, 1, 2, 10] and k = 8, the ans should be true, because subarray sum[5,1,2] = 8 is divisibke by 8

Approach:

This problem is very similar to this problem.
Again this problem can be solved using the prefix sum method. Every time we will mark the value of modulo that can be found from (current Prefix sum value modulo K)

let's illustrate,

See, how it works, we build a prefix sum array, after that every time we will mark the value of (pSum%k with its position) if we haven't met with this value-position before. See, here first we got remainder 1 in position 0 after that again we got the same remainder at position 3, that means,3-0 = 3 elements after position 0, their sum will be divisible by k. 
Lets, check [5,1,2] from position 1 to 3, their sum is 8 that is divisible by 8

Simple code, after each operation, we have to check the length of the subarray is greater than or equal to two(2) or not.

Maximum Size Subarray Sum Equals k

Problem:

Given an array nums and a target value k, find the maximum length of a subarray that sums to k.

If there isn't one, return 0 instead.

Example:

nums = [1, -1, 5, -2, 3], k = 3, maximum length should be 4, that is [1,-1,5,-2,3]

nums = [-2, -1, 2, 1], k = 1 maximum length should be 2, that is [-1,2]

Approach: This Problem is very similar to this problem, Just we have to modify it a little bit. Again we will solve it using the Prefix sum method. in every ith position, we will check have we met the (pSum - k) value previously or not, then simply we will choose maximum length (i-j+1) Simple code:

Firstly we set 0 value to -1, then we check every time we have met it or not.

Minimum Size Subarray Sum greater or equal K

Problem:

Given an array of positive integers nums and a positive integer target, return the

minimal length of a contiguous subarray of which the sum is greater than or equal(>=) to target. If there is no such subarray, return 0 instead.

Example, nums = [2,3,1,2,4,3] and target = 7, the minimum subarray length should be 2, that is [4,3]

Approach:

We can solve this problem using two methods. The first one is the Prefix sum + Binary search approach and another one is the Two pointer approach.

Let's discuss the first one,

We all know how Prefix sum works, in every ith position it will store the previous all elements sum including current(ith) position, right?

So, now let's illustrate it.

After building the prefix sum array we have to make some observations.

~How can we get our target value !
~How can we choose minimal length subarray
Suppose we're at a position 'i' and we need 'X' number, we can get it if and only if there is another value 'Y', that is,
Current[i] - X = Y
It's really easy to understand,
     prefix[i] - prefix[j] = target

=>prefix[i] - target = prefix[j]
Hence the prefix array is sorted, for finding the prefix[j] we can do a binary search( upper bound can do this). If we get the position of prefix[j] we can simply update our answer by (i-j+1)

Time Complexity : O(n*log(n)), log(n) for binary search

Simple Code:

Subarray Sums Divisible by K

Problem:

Given an array "nums" of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by k.

Example, nums = [4,5,0,-2,-3,1], k = 5 ans should be 7

[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3] the sum of this subarrays are divisible by 5.

Approach:

This Problem is similar to Subarray Sum Equals K , the difference is here  we have to find number of subarray is divisible by K.

Approach will be same as before, in every position of given array we will check have we already met its remainder (pSum%k)  or not.

Similarly we will maintain A prefix sum and a Hashing Map.

Corner Case: Hense, there will be negative value, so its possible to have negative ramainder, so we have to make it positive by adding +k.

Simple Code:

Subarray Sums Divisible by K

Again, we count every occurences of remaider that we already met.

Now we will see how it works actually.

See, we calculating result help with prefix sum. Means that every time we need index 'j'(j < i) that is (pSum[i] - pSum[j])%k==0

Now from modular arithmatics, 

     (pSum[i] - pSum[j]) = k*X

=>pSum[j] = pSum[i] - k*X

=>pSum[j] % k = (pSum[i] - k*X)%k [taking mod both sides]

=>pSum[j] % k = (pSum[i] % k - k*X%k)%k [distributive]

=>pSum[j] % k = (pSum[i]%k)%k [k*X%k will be 0]

=>pSum[j] % k = pSum[i]%k

so, we need to find the occurences of pSum[j]%k.

Subarray Sums Equals K

Problem:

Given an array of integers 'nums' and an integer 'K', return the total number of continuous subarrays whose sum equals to 'K'.

Example, [1,2,3], K = 3, total subarray whose sum equal to 3 will be 2, thats are [1,2] and [3]

Approach:

We can solve this problem by a little observation, just think we need k - currnet value instead of k. We can maintain a prefix sum value and a "seen" hashmap, "seen" will tell us how many times we already found the  value we need (current prefix sum - K value)

Basicaly The Hashmap "Seen" we used as a frequency table, every time it store the occurences of 

current prefix sum - K value.

We collect the occurences of 

current prefix sum - K and we store in ans variable.

Now the question is why we need to count the occurences of the value we previously met !

See, in the second example the last Prefix value is 21,

now if we count 21-7 = 14 only 1 , thats not valid because if we include [-2,2] with [1,4] that will be another valid subarray.

When we search for 14 in Prefix sum array we find it on 2 and 4 indexes.

The logic here is that 14 + 7 = 21 so the array between indexes

~ 3 to 7 (-2 2 1 4 2)

~ 5 to 7 both have sum 7 ( 1 4 2)

The sum is still 7 in this case because there are negative numbers that balance up.

So if we consider count++ we will have one count less as we will consider only array 5 to 7 but now we know that 14 sum occured earlier too so even that needs to be added up so occurences of (sum-k).

Simple code: