Find sum of Series with n-th term as n^2 β (n-1)^2
We are given an integer n and n-th term in a series as expressed below:
Tn = n2 - (n-1)2
We need to find Sn mod (109 + 7), where Sn is the sum of all of the terms of the given series and,
Sn = T1 + T2 + T3 + T4 + ...... + Tn
Examples:
Input : 229137999 Output : 218194447 Input : 344936985 Output : 788019571
Let us do some calculations, before writing the program. Tn can be reduced to give 2n-1 . Letβs see how:
Given, Tn = n2 - (n-1)2 Or, Tn = n2 - (1 + n2 - 2n) Or, Tn = n2 - 1 - n2 + 2n Or, Tn = 2n - 1.
Now, we need to find ?Tn.
?Tn = ?(2n β 1)
We can simplify the above formula as,
?(2n β 1) = 2*?n β ?1
Or, ?(2n β 1) = 2*?n β n.
Where, ?n is the sum of first n natural numbers.
We know the sum of n natural number = n(n+1)/2.
Therefore, putting this value in the above equation we will get,
?Tn = (2*(n)*(n+1)/2)-n = n2
Now the value of n2 can be very large. So instead of direct squaring n and taking mod of the result. We will use the property of modular multiplication for calculating squares:
(a*b)%k = ((a%k)*(b%k))%k
Below is the implementation of above idea:
CPP
// CPP program to find sum of given // series. #include<bits/stdc++.h> using namespace std; #define mod 1000000007 // Function to find sum of series // with nth term as n^2 - (n-1)^2 long long findSum( long long n) { return ((n%mod)*(n%mod))%mod; } // Driver code int main() { long long n = 229137999; cout << findSum(n); return 0; } |
Java
// Java program to find sum of given // series. public class FINDSUM { static long mod = 1000000007 ; public static long findSum( long n) { return ((n % mod) * (n % mod)) % mod; } public static void main(String[] args) { long n = 229137999 ; System.out.print (findSum(n)); } } // Contributed by _omg |
Python 3
# Python program to find sum of given # series. mod = 1000000007 def findSum(n): return ((n % mod) * (n % mod)) % mod # main() n = 229137999 print (findSum(n)) # Contributed by _omg |
C#
// C# program to find sum of given // series. using System; class GFG { static long mod = 1000000007; static long findSum( long n) { return ((n % mod) * (n % mod)) % mod; } public static void Main() { long n = 229137999; Console.Write (findSum(n)); } } // This code is contributed by _omg |
PHP
<?php // PHP program to find // sum of givenseries. $mod = 1000000007; // Function to find sum of series // with nth term as n^2 - (n-1)^2 function findSum( $n ) { global $mod ; return (( $n % $mod ) * ( $n % $mod )) % $mod ; } // Driver code $n = 229137999; echo (findSum( $n )); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to find sum of given series. let mod = 1000000007; function findSum(n) { return ((n % mod) * (n % mod)) % mod + 1; } let n = 229137999; document.write(findSum(n)); </script> |
Output:
218194447
Time Complexity: O(1)
Auxiliary Space: O(1)