Suma de series hasta el N-ésimo término cuyo i-ésimo término es i^k – (i-1)^k

Posted on by Rudeus Greyrat

Valor dado de N y K. La tarea es encontrar la suma de la serie hasta el N-ésimo término cuyo i-ésimo término está dado por T i = i k + (i – 1) k . Dado que la suma de la serie puede ser muy grande, calcule su suma módulo 1000000007.

Ejemplo: 

Input : n = 5, k = 2
Output: 25
first 5 term of the series :
T1 = ( 1 )2 + ( 1 - 1 )2  = 1
T2 = ( 2 )2 + ( 2 - 1 )2  = 3
T3 = ( 3 )2 + ( 3 - 1 )2  = 5
T4 = ( 4 )2 + ( 4 - 1 )2  = 7
T4 = ( 5 )2 + ( 5 - 1 )2  = 9
Sum of the series = 1 + 3 + 5 + 7 + 9 =  25


Input: n = 4, k = 3
Output : 64
First 4 term of the series:
T2 = ( 1 )3 + ( 1 - 1 )3  = 1
T3 = ( 2 )3 + ( 2 - 1 )3  = 7
T4 = ( 3 )3 + ( 3 - 1 )3  = 19
T4 = ( 4 )3 + ( 4 - 1 )3  = 37
Sum of the series = 1 + 7 + 19 + 37 = 64

Enfoque ingenuo Una solución simple es generar todos los términos hasta n y sumarlos. La complejidad temporal será O(N). Dado que N es muy grande, el enfoque dará como resultado TLE. 

Mejor solución 
Echemos un vistazo al patrón de la serie. 

Considere N = 4, K = 3 
Entonces la serie será: 
1 3 – (1 – 1) 3 + 2 3 – (2 – 1) 3 + 1 3 – (3 – 1) 3 + 4 3 – (4 – 1) 3
es decir 1 3 – 0 3 + 2 3 – 1 3 + 3 3 – 2 3 + 4 3 – 3 3
Reescribiendo las mismas potencias juntas, obtenemos. 
0 3 + 1 3 – 1 3 + 2 3 – 2 3 + 33 – 3 3 + 4 3 
es decir , 0 3 + 1 3 – 1 3 + 2 3 – 2 3 + 3 3 – 3 3 + 4 3 
Así que el resultado final será 4 3 (ie n k ) 
Por lo tanto, la fórmula final es N K 
 

A continuación se muestra la forma ingenua de calcular N K .  

C++

// CPP Code to find sum of series
 
#include <bits/stdc++.h>
using namespace std;
 
#define MOD 1000000007
 
// function to calculate sum of series
int calculateSum(int n, int k)
{
    // Initialize result
    long long res = 1;
 
    // loop to calculate n^k
    for (int i = 0; i < k; i++) {
        res = (res * n) % MOD;
    }
 
    return res;
}
 
// Driver code
int main()
{
    int n = 4, k = 3;
 
    // function calling
    cout << calculateSum(n, k);
 
    return 0;
}

Java

// JAVA code to find
// Sum of series
 
class GFG {
 
    // function to calculate sum of series
    static long calculateSum(int n, int k)
    {
 
        // Initialize res and MOD
 
        long res = 1;
        long MOD = 1000000007;
 
        // loop to calculate n^k % MOD
        for (int i = 0; i < k; i++) {
 
            res = (res * n) % MOD;
        }
 
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int n = 4;
        int k = 3;
        System.out.print(calculateSum(n, k));
    }
};

Python3

# Python 3 code to find
# the sum of series
 
 
# function to calculate sum of series
def calculateSum(n, k):
     
    # initialize res
    res = 1
  
    # initialize MOD
    MOD = 1000000007
     
    # loop to calculate n ^ k % MOD
    for i in range ( 0, k):
        res = ( res * n ) % MOD
 
    return res
 
 
# Driver code
n = 4
k = 3
 
# function calling
print(calculateSum(n, k))

C#

// C# code to find the
// sum of the series
 
using System;
 
class GFG {
    // function to calculate sum of the series
    static int calculateSum(int n, int k)
    {
        // initialize res
        int res = 1;
 
        // Initialize MOD
        int MOD = 1000000007;
 
        // loop to calculate n^k % MOD
        for (int i = 0; i < k; i++) {
 
            res = (res * n) % MOD;
        }
        return res;
    }
 
    // Driver Code
    static public void Main()
    {
        int n = 4;
        int k = 3;
 
        // function calling
        Console.WriteLine(calculateSum(n, k));
    }
}

PHP

// PHP code to find
// the sum of series
 
<?php
  
// function to calculate sum of the series
function calculateSum($n, $k)
{
      
    // Initialize res
    $res = 1;    
 
    // Initialize MOD
    $MOD = 1000000007;
 
    // loop to calculate n^k % MOD
    for( $i=0 ; $i < $k ; $i++)
    {
          $res =( $res * $n )% $MOD;
    }
    return $res;
}
  
// Driver Code
$n = 4;
$k = 3;
  
// function calling
echo calculateSum($n, $k);
 
?>

Javascript

<script>
// javascript Code to find sum of series
const MOD = 1000000007;
 
// function to calculate sum of series
function calculateSum( n,  k)
{
 
    // Initialize result
    let res = 1;
 
    // loop to calculate n^k
    for (let i = 0; i < k; i++)
    {
        res = (res * n) % MOD;
    }
    return res;
}
 
// Driver code
    let n = 4, k = 3;
 
    // function calling
    document.write( calculateSum(n, k));
     
    // This code is contributed by gauravrajput1
 
</script>
Producción

64

Complejidad de tiempo: O(k)

Espacio Auxiliar: O(1)
N K se puede calcular en O(log N) usando Exponenciación Modular .

C++

// CPP Code to find sum of series
#include <bits/stdc++.h>
using namespace std;
 
#define MOD 1000000007
 
// function to calculate sum of series
int calculateSum(int n, int k)
{
    // initialize res
    long long res = 1;
 
    // loop to calculate n^k % MOD
    // using modular Arithmetic
    while (k > 0) {
 
        // if k is odd
        // multiply it with res
        if (k & 1)
            res = (res * n) % MOD;
 
        // k must be even now
        // change k to k/2
        k = k / 2;
 
        // change n to  n^2
        n = (n * n) % MOD;
    }
    return res;
}
 
// Driver code
int main()
{
    int n = 4, k = 3;
    cout << calculateSum(n, k);
    return 0;
}

Java

// JAVA code to find sum of series
 
class GFG {
 
    // Function to calculate sum of series
    static long calculateSum(int n, int k)
    {
 
        // initialize res and MOD
        int res = 1;
        int MOD = 1000000007;
 
        // loop to calculate n^k % MOD
        // using modular Arithmetic
        while (k > 0) {
            // if k is odd
            // multiply n with res
            if ((k & 1) == 1)
                res = (res * n) % MOD;
 
            // k must be even now
            // change k to k / 2
            k = k / 2;
 
            // change n to n^2
            n = (n * n) % MOD;
        }
        return res;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 4, k = 3;
        System.out.print(calculateSum(n, k));
    }
};

Python3

# Python code to calculate sum of series
 
# function to calculate sum of series
def calculateSum(n, k):
     
    # Initialize res
    res = 1
    
    # initialize MOD
    MOD = 1000000007
     
 
    # loop to calculate n ^ k % MOD
    # using Modular arithmetic
    while k > 0 :
 
          # if k is odd
          # Multiply n with res  
          if ( k & 1 ) == 1 :
              res = ( res * n ) % MOD
 
 
          # k must be even now
          # change k to k / 2
          k = k // 2
   
          # change n to n ^ 2
          n =( n * n ) % MOD
           
 
    return res
 
 
# Driver code
 
n = 4
k = 3
 
print(calculateSum(n, k))

C#

// C# code to calculate
// sum of series
 
using System;
 
class GFG {
 
    // Function to calculate sum of series
    static int calculateSum(int n, int k)
    {
        int res = 1; // Initialize res
 
        int MOD = 1000000007;
 
        // Loop to calculate n^k % MOD
        while (k > 0) {
            // If y is odd
            // multiply  res with n
            if ((k & 1) == 1)
                res = (res * n) % MOD;
 
            // k must be even now
            // change k to k/2
            k = k / 2;
 
            // change n to n^2
            n = (n * n) % MOD;
        }
        return res;
    }
 
    // Driver Code
    static public void Main()
    {
        int n = 4;
        int k = 3;
 
        // Function calling
        Console.WriteLine(calculateSum(n, k));
    }
}

PHP

// PHP code to calculate
// Sum of series
 
<?php
  
// Function to calculate sum of series
function calculateSum($n, $k)
{
      
    // Initialize res
    $res = 1;    
 
    // Initialize MOD
    $MOD = 1000000007;
 
    // Loop to calculate n^k % MOD
    // using Modular arithmetic
    while ($k > 0)
    {
          
        // If y is odd
        // multiply with result
        if ($k & 1)
            $res = ( $res * $n ) % $MOD;
  
        // k must be even now
        // Change k to k/2 
        $k = $k / 2;
          
        // Change n to n^2
        $n =( $n * $n ) % $MOD;
    }
    return $res;
}
  
// Driver Code
$n = 4;
$k = 3;
 
// Function calling
echo calculateSum($n, $k);
 
?>

Javascript

<script>
// javascript code to find sum of series
 
    // Function to calculate sum of series
    function calculateSum(n, k)
    {
 
        // initialize res and MOD
        let res = 1;
        let MOD = 1000000007;
 
        // loop to calculate n^k % MOD
        // using modular Arithmetic
        while (k > 0)
        {
         
            // if k is odd
            // multiply n with res
            if ((k & 1) == 1)
                res = (res * n) % MOD;
 
            // k must be even now
            // change k to k / 2
            k = parseInt(k / 2);
 
            // change n to n^2
            n = (n * n) % MOD;
        }
        return res;
    }
 
    // Driver code
    let n = 4, k = 3;
    document.write(calculateSum(n, k));
 
// This code is contributed by gauravrajput1
</script>
Producción

64

Complejidad de tiempo: O (log n)

Complejidad espacial : O (1) ya que usa variables constantes
 

Publicación traducida automáticamente

Artículo escrito por ihritik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *