help me understand the mod

this question from hackerrank(https://www.hackerrank.com/challenges/sam-and-substrings)… requires us to print the sum of all possible substrings, (input is a string of digits), (123 => 1, 2, 3, 12, 13, 123 => 164) so first i tried brute force method (later i was able to come up with an O(N) algo wich pruned unneccassary operations) to identify all n^2 pairs i, j, and then found sum[i, j] (sum of substr starting at i, ending at j), since ans could be large, we had to print ans%10^9,
so utilising the fact that (a + b) x = a x + b % x

i did :

    long sum=0;
    for(i = 0, i < s.size(), i++)
    {
        dp[i] = arr[i];
        sum = sum % 1000000007;
        sum += dp[i];
    
        for(j = i+1, j < s.size(), j++)
        {
            dp[j] = ((dp[j-1]% 1000000007)*10 + arr[j] ) % (1000000007);
            sum += dp[j];
        }
}
//    cout sum;

the code works fine for sample tests but fails, when i submit it…
any suggestions where i am going wrong…
full code :
http://ideone.com/0NXG72

Bro, (a + b) % n = ((a % n) + (b % n)) % n, so correct it.

1 Like

Hi rb08,

consider you code you are doing (a + b) x = a x + b % x But (a+b)%x can never be greater than or equal to x and in right side a%x will be 0 to x-1 and b%x will be 0 to x-1 then there sum may exceed x which is not allowed hence after doing it take mode of there summation too.

well you can find on google some property of mod but let me tell you in short:-

for addition (a+b)%n = ((a%n)+(b%n))%n

for subtraction (a-b)%n when a > b then = ((a%n)-(b%n)+n)%n

for multiplication (ab)%n = ((a%n)(b%n))%n

for division it is complex there are some method to do it. :frowning:

1 Like

thanks fellas, just got AC, after following your advice, i am little weak at number theory, combinatorics,… any resources you might wanna share??

Yes brother, the Modulus operation is a very cool operation, specially when the problem statement says "Print Answer % (10^7 + 7).

So refer to this link to learn cool new thinks, and the proofs are also given so understand them if you have time :slight_smile:

//