Given a sequence whose nth term is
T(n) = n2 – (n – 1)2
The task is to evaluate the sum of first n terms i.e.
S(n) = T(1) + T(2) + T(3) + … + T(n)
Print S(n) mod (109 + 7).
Examples:
Input: n = 3
Output: 9
S(3) = T(1) + T(2) + T(3) = (12 – 02) + (22 – 12) + (32 – 22) = 1 + 3 + 5 = 9
Input: n = 10
Output: 100
Approach: If we try to find out some initial terms of the sequence by putting n = 1, 2, 3, … in T(n) = n2 – (n – 1)2, we find the sequence 1, 3, 5, …
Hence, we find an A.P. where first term is 1 and d (common difference between consecutive
terms) is 2.
The formula for the sum of n terms of A.P is
S(n) = n / 2 [ 2 * a + (n – 1) * d ]
where a is the first term.
So, putting a = 1 and d = 2, we get
S(n) = n2
.
Below is the implementation of above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define ll long int#define MOD 1000000007// Function to return the sum// of the given seriesint sumOfSeries(int n){ ll ans = (ll)pow(n % MOD, 2); return (ans % MOD);}// Driver codeint main(){ int n = 10; cout << sumOfSeries(n); return 0;} |
Java
// Java implementation of the approachclass GFG{ public static final int MOD = 1000000007;// Function to return the sum// of the given seriesstatic int sumOfSeries(int n){ int ans = (int)Math.pow(n % MOD, 2); return (ans % MOD);}// Driver codepublic static void main(String[] args){ int n = 10; System.out.println(sumOfSeries(n));}}// This code is contributed by Code_Mech. |
Python3
# Python 3 implementation of the approachfrom math import powMOD = 1000000007# Function to return the sum# of the given seriesdef sumOfSeries(n): ans = pow(n % MOD, 2) return (ans % MOD)# Driver codeif __name__ == '__main__': n = 10 print(int(sumOfSeries(n)))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG{ const int MOD = 1000000007;// Function to return the sum// of the given seriesstatic int sumOfSeries(int n){ int ans = (int)Math.Pow(n % MOD, 2); return (ans % MOD);}// Driver codepublic static void Main(){ int n = 10; Console.Write(sumOfSeries(n));}}// This code is contributed // by Akanksha Rai |
PHP
<?php// PHP implementation of the approach $GLOBALS['MOD'] = 1000000007; // Function to return the sum // of the given series function sumOfSeries($n) { $ans = pow($n % $GLOBALS['MOD'], 2); return ($ans % $GLOBALS['MOD']); } // Driver code $n = 10; echo sumOfSeries($n); // This code is contributed by Ryuga?> |
Javascript
<script>// javascript program for the above approachlet MOD = 1000000007;// Function to return the sum// of the given seriesfunction sumOfSeries(n){ let ans = Math.pow(n % MOD, 2); return (ans % MOD);}// Driver Code let n = 10; document.write(sumOfSeries(n));</script> |
100
Time Complexity: O(1) because calculation square of a number using pow function takes constant time.
Auxiliary Space: O(1), since no extra space has been taken.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
