Unable to understand -> DIVISIBLE SUBARRAYS

#1

Hello, I am getting difficulty in understanding the problem and test cases, Please help. Thanks in advance. :slight_smile:

#2

@saurabhpandey59373
Let us understand the problem using an example
Consider this testcase.
1
5
1 2 3 4 5

Here , no of testcases = 1
N = 5 (Size of array)
Array , A = { 1, 2, 3, 4, 5}

A subarray is a part of the array which is continuous.
We can generate many subarrays from this given array and if we add all the elements in each subarray , we would have a sum of each subarray. We need to find the subarrays whose sum are divisible by N = 5.
That is ,
Subarrays { 2, 3} , { 5 } , { 1, 2, 3, 4} , { 1, 2, 3, 4, 5} and ofcourse the NULL subarray = { } all have sum that is divisible by N = 5.
We have to find the total number of such subarrays in optimum time.
As per the problem constraints , N can be as large as 10^5. So clearly we cannot use the standard approach of generating subarrays using 2 loops as it would be a O(n^2) approach which clearly would give us TLE due to the constraints.
You need to figure out an optimal solution to approach this problem.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.