Given two very large numbers L and R where L ? R, the task is to compute the sum of all the natural numbers from L to R. The sum could be large so print the sum % 1000000007.
Examples:
Input: L = “8894” R = “98592”
Output: 820693329
Input: L = “88949273204” R = “98429729474298592”
Output: 252666158
Approach:
- Let sum(N) is a function that returns the sum of first N natural numbers.
- The sum of the first N natural numbers is sum(N) = (N * (N + 1)) / 2.
- The sum of the numbers in the range between L to R will be RangeSum = sum(R) – sum(L – 1)
- The answer is calculated with the modulo 109 + 7, So,
mod = 109 + 7
RangeSum = (sum(R) – sum(L-1) + mod)%mod;
This can be also written as RangeSum = (sum(R)%mod – sum(L-1)%mod + mod)%mod;
Now, sum(R) % mod can be written as ((R * (R + 1)) / 2) % mod
Or ((R % mod) * ((R + 1) % mod) * invmod(2)) % mod
Since R is large, the modulo of R can be calculated as described here.
The value of inversemod(2) = 500000004 which can be calculated using Fermat’s little theorem.
Similarly, sum(L – 1) % mod can also be calculated.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define mod 1000000007// Value of inverse modulo// 2 with 10^9 + 7const long long inv2 = 500000004;// Function to return num % 1000000007// where num is a large numberlong long int modulo(string num){ // Initialize result long long int res = 0; // One by one process all the // digits of string 'num' for (long long int i = 0; i < num.length(); i++) res = (res * 10 + (long long int)num[i] - '0') % mod; return res;}// Function to return the sum of the// integers from the given range// modulo 1000000007long long int findSum(string L, string R){ long long int a, b, l, r, ret; // a stores the value of // L modulo 10^9 + 7 a = modulo(L); // b stores the value of // R modulo 10^9 + 7 b = modulo(R); // l stores the sum of natural // numbers from 1 to (a - 1) l = ((a * (a - 1)) % mod * inv2) % mod; // r stores the sum of natural // numbers from 1 to b r = ((b * (b + 1)) % mod * inv2) % mod; ret = (r % mod - l % mod); // If the result is negative if (ret < 0) ret = ret + mod; else ret = ret % mod; return ret;}// Driver codeint main(){ string L = "88949273204"; string R = "98429729474298592"; cout << findSum(L, R) << endl; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static long mod = 1000000007;// Value of inverse modulo// 2 with 10^9 + 7static long inv2 = 500000004;// Function to return num % 1000000007// where num is a large numberstatic long modulo(String num){ // Initialize result long res = 0; // One by one process all the // digits of string 'num' for (int i = 0; i < num.length(); i++) res = (res * 10 + (long)num.charAt(i) - '0') % mod; return res;}// Function to return the sum of the// longegers from the given range// modulo 1000000007static long findSum(String L, String R){ long a, b, l, r, ret; // a stores the value of // L modulo 10^9 + 7 a = modulo(L); // b stores the value of // R modulo 10^9 + 7 b = modulo(R); // l stores the sum of natural // numbers from 1 to (a - 1) l = ((a * (a - 1)) % mod * inv2) % mod; // r stores the sum of natural // numbers from 1 to b r = ((b * (b + 1)) % mod * inv2) % mod; ret = (r % mod - l % mod); // If the result is negative if (ret < 0) ret = ret + mod; else ret = ret % mod; return ret;}// Driver codepublic static void main(String[] args) { String L = "88949273204"; String R = "98429729474298592"; System.out.println(findSum(L, R));}} // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach mod = 1000000007# Value of inverse modulo # 2 with 10^9 + 7 inv2 = 500000004; # Function to return num % 1000000007 # where num is a large number def modulo(num) : # Initialize result res = 0; # One by one process all the # digits of string 'num' for i in range(len(num)) : res = (res * 10 + int(num[i]) - 0) % mod; return res; # Function to return the sum of the # integers from the given range # modulo 1000000007 def findSum(L, R) : # a stores the value of # L modulo 10^9 + 7 a = modulo(L); # b stores the value of # R modulo 10^9 + 7 b = modulo(R); # l stores the sum of natural # numbers from 1 to (a - 1) l = ((a * (a - 1)) % mod * inv2) % mod; # r stores the sum of natural # numbers from 1 to b r = ((b * (b + 1)) % mod * inv2) % mod; ret = (r % mod - l % mod); # If the result is negative if (ret < 0) : ret = ret + mod; else : ret = ret % mod; return ret; # Driver code if __name__ == "__main__" : L = "88949273204"; R = "98429729474298592"; print(findSum(L, R)) ; # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG{static long mod = 1000000007;// Value of inverse modulo// 2 with 10^9 + 7static long inv2 = 500000004;// Function to return num % 1000000007// where num is a large numberstatic long modulo(String num){ // Initialize result long res = 0; // One by one process all the // digits of string 'num' for (int i = 0; i < num.Length; i++) res = (res * 10 + (long)num[i] - '0') % mod; return res;}// Function to return the sum of the// longegers from the given range// modulo 1000000007static long findSum(String L, String R){ long a, b, l, r, ret; // a stores the value of // L modulo 10^9 + 7 a = modulo(L); // b stores the value of // R modulo 10^9 + 7 b = modulo(R); // l stores the sum of natural // numbers from 1 to (a - 1) l = ((a * (a - 1)) % mod * inv2) % mod; // r stores the sum of natural // numbers from 1 to b r = ((b * (b + 1)) % mod * inv2) % mod; ret = (r % mod - l % mod); // If the result is negative if (ret < 0) ret = ret + mod; else ret = ret % mod; return ret;}// Driver codepublic static void Main(String[] args) { String L = "88949273204"; String R = "98429729474298592"; Console.WriteLine(findSum(L, R));}}// This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach let mod = 1000000007; // Value of inverse modulo // 2 with 10^9 + 7 let inv2 = 500000004; // Function to return num % 1000000007 // where num is a large number function modulo(num) { // Initialize result let res = 0; // One by one process all the // digits of string 'num' for (let i = 0; i < num.length; i++) res = (res * 10 + num[i].charCodeAt() - '0'.charCodeAt()) % mod; return res; } // Function to return the sum of the // longegers from the given range // modulo 1000000007 function findSum(L, R) { let a, b, l, r, ret; // a stores the value of // L modulo 10^9 + 7 a = modulo(L); // b stores the value of // R modulo 10^9 + 7 b = modulo(R); // l stores the sum of natural // numbers from 1 to (a - 1) l = ((a * (a - 1)) % mod * inv2) % mod; // r stores the sum of natural // numbers from 1 to b r = ((b * (b + 1)) % mod * inv2) % mod; ret = (r % mod - l % mod); // If the result is negative if (ret < 0) ret = ret + mod; else ret = ret % mod - 6; return ret; } let L = "88949273204"; let R = "98429729474298592"; document.write(findSum(L, R));// This code is contributed by decode2207.</script> |
Output:
252666158
Time Complexity: O(|L| + |R|)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
