Find m-th summation of first n natural numbers.
m-th summation of first n natural numbers is defined as following.
If m > 1 SUM(n, m) = SUM(SUM(n, m - 1), 1) Else SUM(n, 1) = Sum of first n natural numbers.
We are given m and n, we need to find SUM(n, m).
Examples:
Input : n = 4, m = 1 Output : SUM(4, 1) = 10 Explanation : 1 + 2 + 3 + 4 = 10 Input : n = 3, m = 2 Output : SUM(3, 2) = 21 Explanation : SUM(3, 2) = SUM(SUM(3, 1), 1) = SUM(6, 1) = 21
Naive Approach : We can solve this problem using two nested loop, where outer loop iterate for m and inner loop iterate for n. After completion of a single outer iteration, we should update n as whole of inner loop got executed and value of n must be changed then. Time complexity should be O(n*m).
for (int i = 1;i <= m;i++) { sum = 0; for (int j = 1;j <= n;j++) sum += j; n = sum; // update n }
Efficient Approach :
We can use direct formula for sum of first n numbers to reduce time.
We can also use recursion. In this approach m = 1 will be our base condition and for any intermediate step SUM(n, m), we will call SUM (SUM(n, m-1), 1) and for a single step SUM(n, 1) = n * (n + 1) / 2 will be used. This will reduce our time complexity to O(m).
int SUM (int n, int m) { if (m == 1) return (n * (n + 1) / 2); int sum = SUM(n, m-1); return (sum * (sum + 1) / 2); }
Below is the implementation of above idea :
C++
// CPP program to find m-th summation #include <bits/stdc++.h> using namespace std; // Function to return mth summation int SUM( int n, int m) { // base case if (m == 1) return (n * (n + 1) / 2); int sum = SUM(n, m-1); return (sum * (sum + 1) / 2); } // driver program int main() { int n = 5; int m = 3; cout << "SUM(" << n << ", " << m << "): " << SUM(n, m); return 0; } |
Java
// Java program to find m-th summation. class GFG { // Function to return mth summation static int SUM( int n, int m) { // base case if (m == 1 ) return (n * (n + 1 ) / 2 ); int sum = SUM(n, m - 1 ); return (sum * (sum + 1 ) / 2 ); } // Driver code public static void main(String[] args) { int n = 5 ; int m = 3 ; System.out.println( "SUM(" + n + ", " + m + "): " + SUM(n, m)); } } // This code is contributed by Anant Agarwal. |
Python
# Python program to find m-th summation. def SUM (n, m): # base case if m = = 1 : return (n * (n + 1 ) / / 2 ) su = SUM (n, m - 1 ) return (su * (su + 1 ) / / 2 ) # Driver code n = 5 m = 3 print ( "SUM(" + str (n) + ", " + str (m) + "): " + str ( SUM (n, m))) |
C#
// C# program to find m-th summation. using System; class GFG { // Function to return mth summation static int SUM( int n, int m) { // base case if (m == 1) return (n * (n + 1) / 2); int sum = SUM(n, m - 1); return (sum * (sum + 1) / 2); } // Driver Code public static void Main() { int n = 5; int m = 3; Console.Write( "SUM(" + n + ", " + m + "): " + SUM(n, m)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP program to find m-th summation // Function to return // mth summation function SUM( $n , $m ) { // base case if ( $m == 1) return ( $n * ( $n + 1) / 2); $sum = SUM( $n , $m - 1); return ( $sum * ( $sum + 1) / 2); } // Driver Code $n = 5; $m = 3; echo "SUM(" , $n , ", " , $m , "): " , SUM( $n , $m ); // This code is contributed by vt_m. ?> |
Javascript
<script> // javascript program to find m-th summation // Function to return mth summation function SUM( n, m) { // base case if (m == 1) return (n * (n + 1) / 2); let sum = SUM(n, m-1); return (sum * (sum + 1) / 2); } // driver program let n = 5; let m = 3; document.write( "SUM(" + n + ", " + m + "): " + SUM(n, m)); // This code contributed by Rajput-Ji </script> |
Output:
SUM(5, 3): 7260
Space complexity :- O(M)
Contact Us