Sum of all natural numbers from L to R ( for large values of L and R )

0 0 6 minutes read

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 10⁹ + 7, So,

mod = 10⁹ + 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 + 7
const long long inv2 = 500000004;
 
// Function to return num % 1000000007
// where num is a large number
long 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 1000000007
long 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 code
int main()
{
    string L = "88949273204";
    string R = "98429729474298592";
 
    cout << findSum(L, R) << endl;
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
static long mod = 1000000007;
 
// Value of inverse modulo
// 2 with 10^9 + 7
static long inv2 = 500000004;
 
// Function to return num % 1000000007
// where num is a large number
static 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 1000000007
static 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 code
public 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 approach
using System;
     
class GFG
{
static long mod = 1000000007;
 
// Value of inverse modulo
// 2 with 10^9 + 7
static long inv2 = 500000004;
 
// Function to return num % 1000000007
// where num is a large number
static 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 1000000007
static 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 code
public 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 zambiatek!