Hello sir/ma’am
The code i wrote for this question is unable to pass one test case. I am unable to think of the test case that i am missing. Could you please tell which case am i missing??
sharing my code:
Divisible Subarrays
@priyanshi.agarwal3405
In your first loop , write a code like this.
cm[i]=cm[i-1]+arr[i-1];
cm[i]%=n;
mod[i] = (cm[i]+n)%n;
The negative elements in your code were not handled properly.
Further for the freq array , initialise freq[0] = 1 and then start iterating for freq array from i=1 instead of i=0.
Make these changes and try submitting your code again.
Sir, could you please give me an example where negative elements are not handled properly… Also why do we need to initialise freq[0] with 1 ??
sir could you please reply…
@priyanshi.agarwal3405
The reason we initialise freq[0] with 1 is due to the fact that we know there would always be a subarray with sum=0 which would be the subarray with no elements i.e. the NULL subarray. Since we are marking the frequency of subarray sums that we can obtain and we already have a subarray with sum 0 , we mark it so in our frequency array beforehand.
As for your other doubt about the negative elements , consider this .
As you can see , when negative numbers are involved , the value of sum becomes -ve and since we are making a frequency array of sum only and updating it accordingly
freq[ sum ]++ ;
If the value of sum is -ve , this statement will give either a runtime error or access the wrong memory location thus updating the value at the wrong index which will eventually give us a wrong answer. Hence making the value of sum variable positive is important. Now to make it positive , we cannot just add any number to it.
Since we are taking modulo of sum with n , we can add n to sum to make it positive thanks to the modulo properties.
Adding n to the negative value and then taking the modulo with n only makes it positive and within the range. This way we are assured to get the correct answer.
Input :
1
5
-12 -7 -10 -12 -1
Case 1 : When we didn’t include the (sum = (sum + n) % n ) statement i.e. when we get wrong output .
Iteration 1 : Sum = -2
Iteration 2 : Sum = -4
Iteration 3 : Sum = -4
Iteration 4 : Sum = -1
Iteration 5 : Sum = -2
Final Output :
0
Case 2 : When we include the above specified statement to work with the negative numbers .
Iteration 1 : Sum = 3
Iteration 2 : Sum = 1
Iteration 3 : Sum = 1
Iteration 4 : Sum = 4
Iteration 5 : Sum = 3
Final Output :
2
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.
Sir, i think in my code there is no need to initialise freq[0]=1; that is being done automatically. I have initialised the whole freq array with 0 then in loop of lines 20-23 that is being done, as mod[0]=0, so freq[mod[0]]++ will make this value 1.
Secondly, i replaced line 17 which was earlier mod[i]=n-(abs(cm[i])%n) with mod[i]=((cm[i])+n)%n; as you said, still one test case is not passing.
Also, bcoz you were saying so, i initialised freq[0] with 1(though not needed), then also one test case not passing. I think there’s some other error that i am unable to resolve. Please tell me what to do further. Thank you!!
Hi @priyanshi.agarwal3405
Everything is fine in your code. Only you have to add cm[i]=cm[i]%n; after line 13 then your code will pass all the test cases.
Here is your corrected code :
And sir what is the significance of adding this new line?? Could you please explain with the help of an example.
Hi @priyanshi.agarwal3405
See when you are computing cum[i] then there is a case when cum[i] is negative and greater than n, then if you don’t do cum[i]%n then in the else case you add n to cum[i] but as cum[i] < -n then even on adding n it is still negative thereby causing run error. For example if we have array as -11 -5 2 3 5 then cum[1] is -11 and then in the else case mod[1] become -1 which creates run time error at line 25 as index of freq array can not be negative. That is why it is necessary to add cm[i]=cm[i]%n; after line 13.
Is your doubt cleared ? If clear so please mark it as resolved.
Okay sir, got it. Thanks!!