Last Updated: 10 Dec, 2021
Subarray Remainder
Moderate
Asked in companies
You are given an integer array 'A' of length 'N'. Your task is to find a subarray A[L, R] for which following conditions hold:
1 <= L < R <= N.
Let S = A[L] + A[L+1] + …. + A[R-1] + A[R], then S % K = 0.
Your task is to find whether there exists a subarray for which above conditions hold. If such a subarray is found, return 1, else return 0.
Input Format:
The first line contains 'T', denoting the number of tests.
For each Test :
The first line contains two space-separated integers, 'N' and 'K', denoting the size of array and number K, respectively.
The second line contains an array 'A' of length 'N'.
Output Format:
For each test, print an integer (either 0 or 1), denoting whether a subarray fulfilling given conditions is found.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'K' <= 10^9
0 <= A[i] <= 10^9 i ∈ (1, N)
Note - Sum of 'N' over all test cases does not exceed 10^5.
Time Limit: 1 sec
Approaches
Approach: Run two nested loops to select each possible subarray (of length at least 2), and if its sum is a multiple of value 'K', return 1. At last, if no subarray is found, return 0.
Algorithm:
- Iterate a for loop, i = 1 to N.
- Initialize sum with A[i].
- Iterate another for loop, j = i + 1 to N.
- Add A[j] into sum.
- If the sum becomes a multiple of K, return 1.
- Return 0.
Approach: As we know, if 'S' is a multiple of K, then (A+S)%K = A%K.
Use this property on the prefix sum of array 'A'. Let's assume that our answer is subarray A[L, R], whose sum is a multiple of K; then we can say that [ sum(A[1, L-1]) % K = sum(A[1, R]) % K ].
Maintain a hashmap and store the remainder of the prefix sum for each index 'i'. For each 'i', first check if the same remainder has occurred earlier. If the remainder has occurred, fetch its index, and if there are at least two elements (i-th inclusive) after that index, return 1.
If the remainder has not previously occurred, store its index (currently 'i') in the hashmap and process the remaining array.
If no repeated remainder is found, return 0.
Algorithm:
- Initialize an empty hashmap.
- Initially, prefix sum and remainder both are assumed 0, so insert an entry for (remainder = 0) in the hashmap.
- Iterate a for loop, i = 1 to N.
- Add A[i] into the prefix sum and calculate the remainder.
- If the remainder has already occurred in hashmap.
- If the index of remainder is earlier than i-1.
- Return 1.
- If the index of remainder is earlier than i-1.
- Else, mark the position of the remainder as index ‘i’ in the hashmap.
- Return 0.