How do I deal with negative numbers? I think because of that my code seems to be incorrect. Here’s my code - https://ide.codingblocks.com/s/114925
Divisible subarrays prob
@ranjanpanda
You are right. The problem occurs in case when the cumulative sum becomes negative because of -ve integers in the array. Also , you don’t really need the helper array.
Try something like
for i = 0 to n
{
cin >> a[i]
sum = (sum+a[i]) % n
sum += n
sum %= n
}
The statement sum += n is to make the sum positive in case it ever gets -ve. In case it were positive only , this statement wouldn’t make any difference as we are taking the modulo in the next step only so it wouldn’t harm us anyway.
1 Like
SIr can you please explain it with an example?
@ranjanpanda
Input :
1
5
-2 -7 -10 -12 -1
Expected Output :
2
Output without the (sum = (sum + n) % n ) statement :
0
Explanation :
Let us first consider the wrong output i.e. when we are not adding n to sum before taking modulo.
The value of sum at each point in this case will be
Iteration 1 : Sum = -2
Iteration 2 : Sum = -4
Iteration 3 : Sum = -4
Iteration 4 : Sum = -1
Iteration 5 : Sum = -2
Now consider the correct method i.e. when we add n to sum before taking modulo
sum = (sum + n) % n .
The value of sum at each point in this case will be
Iteration 1 : Sum = 3
Iteration 2 : Sum = 1
Iteration 3 : Sum = 1
Iteration 4 : Sum = 4
Iteration 5 : Sum = 3
As you can see , the addition is done to make the sum positive so that we can properly compute our result as taking modulo with negative numbers gives wrong answers.
Since our sum will always be less than n , as we are taking modulo with n only , we should add n to sum to make it positive and then take the modulo so that we get right answers.
1 Like
What if the first number itself is greater than n and negative eg. instead of -2 we had -12.
@ranjanpanda
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
This question has been a very tricky one to me. My last doubt is how is it ensured that by adding n it will give us the correct answer, like to just deal with negative numbers, we have added n. But what’s the logic behind it?
@ranjanpanda
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.
Let’s say you have to take the modulo of sum integer y with x. You are not sure whether y is positive or negative. If you just write
ans = y % x ;
This will work if y were positive but will give the wrong answer if y were negative.
To cover both the cases , add x to y first
y = y + x;
and then take the modulo with x
ans = y % x;
or simply in one step only
ans = ( y + x ) % x;
If you add the same number you take the modulo with , you get the correct answer if y were negative. In case y was already positive , the extra added x wouldn’t make any difference at all and would still produce the same result.
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.