Encuentra la m-ésima suma de los primeros n números naturales.

La m-ésima suma de los primeros n números naturales se define de la siguiente manera.
 

If m > 1
  SUM(n, m) = SUM(SUM(n, m - 1), 1)
Else 
  SUM(n, 1) = Sum of first n natural numbers.

Nos dan m y n, necesitamos encontrar SUM(n, m).
Ejemplos: 
 

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

Enfoque ingenuo: podemos resolver este problema utilizando dos bucles anidados, donde el bucle externo itera para m y el bucle interno itera para n. Después de completar una sola iteración externa, debemos actualizar n ya que todo el ciclo interno se ejecutó y el valor de n debe cambiarse en ese momento. La complejidad del tiempo debe ser 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
}

Enfoque eficiente: 
podemos usar una fórmula directa para la suma de los primeros n números para reducir el tiempo. 
También podemos usar la recursividad. En este enfoque m = 1 será nuestra condición base y para cualquier paso intermedio SUM(n, m), llamaremos SUM (SUM(n, m-1), 1) y para un solo paso SUM(n, 1) = n * (n + 1) / 2 se utilizará. Esto reducirá nuestra complejidad de tiempo a 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);
}

A continuación se muestra la implementación de la idea anterior:
 

// 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 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.

// 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 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.
?>

<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>

Producción: 
 

SUM(5, 3): 7260

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.