Given a positive integer n. Find the sum of the first n term of the series
12, 105, 1008, 10011, …..
Examples:
Input: n = 4
Output: 11136Input: n = 7
Output: 11111187
Approach:
The sequence is formed by using the following pattern. For any value N-
![S_{n} = \frac{10}{9}*(10^{n}-1) + \frac{n}{2}[3n+1]](https://neveropen.co.uk/wp-content/uploads/2023/11/rubhabha_quicklatex.com-bab5a58de1ed30a6d06285d4d16852a4_l3.png "Rendered by QuickLaTeX.com")
The above solution can be derived following a series of steps:
Given Series-
12 + 105 + 1008 + 10011 +…….
10 + 2 + 100 + 5 + 1000 + 8 + 10000 + 11 +……..
(10 + 100 + 1000 + 10000+……) + (2 + 5 + 8 + 11+……) -(1)
The first term in the above equation is Geometric progression and the second term is Arithmetic progression.
G.P. =
where a is the first term a, r is the common ratio and n is the number of terms.A.P. =
where a is the first term a, a is the common difference and n is the number of terms.So after substituting values in equation of G.P. and A.P. and substituting corresponding equations in equation (1) we get,
So,
![\frac{n}{2}[2a +(n - 1)d]](https://neveropen.co.uk/wp-content/uploads/2023/11/rubhabha_quicklatex.com-0a92ec2006964c5113a7ff962b91e63e_l3.png "Rendered by QuickLaTeX.com")
![10*\frac{10^{n}-1}{10-1} + \frac{n}{2}[2*2+(n-1)*3]](https://neveropen.co.uk/wp-content/uploads/2023/11/wardslaus_quicklatex.com-1a0d61ab8bf5f44d0974626d8ecbae92_l3.png "Rendered by QuickLaTeX.com")
![\frac{10}{9}*10^{n}-1 + \frac{n}{2}[4+3n-3]](https://neveropen.co.uk/wp-content/uploads/2023/11/neveropen_quicklatex.com-164cd31945f5d9a9636a70f1914f9125_l3.png "Rendered by QuickLaTeX.com")
![\frac{10}{9}*(10^{n}-1) + \frac{n}{2}[3n+1]](https://neveropen.co.uk/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-f2e77c1fbf736e737ee7af37eb957f1d_l3.png "Rendered by QuickLaTeX.com")
Illustration:
Input: n = 4
Output: 11136
Explanation:![S_{n} = \frac{10}{9}*(10^{4}-1) + \frac{4}{2}[3*4+1]](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%20376%2032'%3E%3C/svg%3E "Rendered by QuickLaTeX.com")
This gives ans 11136.
![S_{n} = \frac{10}{9}*(10^{4}-1) + \frac{4}{2}[3*4+1]](https://neveropen.co.uk/wp-content/uploads/2023/11/rubhabha_quicklatex.com-9c6dbf271999e4fa487212f434b6c74a_l3.png "Rendered by QuickLaTeX.com")
![S_{n} = \frac{10}{9}*(9999) + \frac{4}{2}[13]](https://neveropen.co.uk/wp-content/uploads/2023/11/wardslaus_quicklatex.com-badcc4ba5ba358cb56ed942891684ce4_l3.png "Rendered by QuickLaTeX.com")
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>#define ll long longusing namespace std;// Function to return sum of// N term of the seriesll findSum(ll n){ ll x = 10 * (pow(10, n) - 1) / 9; ll y = n * (3 * n + 1) / 2; return x + y;}// Driver Codeint main(){ ll n = 4; cout << findSum(n); return 0;} |
Java
// Java program to implement// the above approachclass GFG { // Function to return sum of // N term of the series static int findSum(int n) { int x = (int)(10 * (Math.pow(10, n) - 1) / 9); int y = n * (3 * n + 1) / 2; return x + y; } // Driver Code public static void main(String args[]) { int n = 4; System.out.println(findSum(n)); }}// This code is contributed by saurabh_jaiswal. |
Python3
# Python program to implement# the above approach# include <bits/stdc++.h># define ll long long# Function to return sum of# N term of the seriesdef findSum(n): x = 10 * ((10 ** n) - 1) / 9 y = n * (3 * n + 1) / 2 return int(x + y)# Driver Coden = 4print(findSum(n))# This code is contributed by saurabh_jaiswal. |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to return sum of // N term of the series static int findSum(int n) { int x = (int)(10 * (Math.Pow(10, n) - 1) / 9); int y = n * (3 * n + 1) / 2; return x + y; } // Driver Code public static void Main() { int n = 4; Console.Write(findSum(n)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to return sum of // N term of the series function findSum(n) { let x = 10 * (Math.pow(10, n) - 1) / 9; let y = n * (3 * n + 1) / 2; return Math.floor(x) + Math.floor(y); } // Driver Code // Get the value of N let N = 4; document.write(findSum(N));// This code is contributed by Potta Lokesh </script> |
11136
Time Complexity: O(logN) since it is using pow function
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!
