Subarray Remainder

Moderate

0/80

Average time to solve is 15m

Contributed by

3 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

1
0

Explanation for Sample Input 1:

For case 1:
If L = 2 and R = 3, both of the given conditions are true.
S = 2 + 4 = 6.
S % K = 6 % 6 = 0.

For Case 2:
No subarray is found for which S % K = 0.

Sample Input 2:

Sample Output 2:

1
1
0

Hint 1

Hint 2

Can you check for each subarray sum?

Approaches (2)

Approach 1

Approach 2

Brute force

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.

Time Complexity

O(N ^ 2), where 'N' is the number of elements in the array 'A'.

We ran two nested loops and checked for each subarray sum. Hence overall time complexity becomes O(N ^ 2).

Space Complexity

O(1).

We are using only constant space. Hence overall space complexity is O(1).

(100% EXP penalty)

Subarray Remainder

Console