Suma de la serie Kn + ( K(n-1) * (K-1)1 ) + ( K(n-2) * (K-1)2 ) + ……. (K-1)n

Posted on by Rudeus Greyrat

Dado un valor K y n, la tarea es encontrar la suma de la siguiente serie:

K n + ( K (n-1) * (K-1) 1 ) + ( K (n-2) * (K-1) 2 ) + ……. (K-1) norte

Ejemplos:  

Input:  n = 3, K = 3
Output: 65
Explanation:
(3*3*3) + (3*3*2) + (3*2*2) + (2*2*2)
= 27 + 18 + 12 + 8
= 65 


Input: n = 4, k = 2
Output: 31
Explanation:
(2*2*2*2) + (2*2*2*1)+ (2*2*1*1) + (2*1*1*1) + (1*1*1*1)
= 16 + 8 + 4 + 2 + 1
= 31
  1. Enfoque simple: O(n 2 ) 
    1. Número total de términos en serie = n+1
    2. Calcula cada término por separado y súmalos:
  2. Segundo Enfoque: O(n)
    Se observa que, dada la serie es Progresión Geométrica , con razón común = (K – 1)/K 
    Entonces, la expresión anterior se puede simplificar como:

  • A continuación se muestra la implementación del enfoque anterior: 

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to return sum
int sum(int k, int n)
{
    int sum
        = pow(k, n + 1)
          - pow(k - 1, n + 1);
 
    return sum;
}
 
// Driver code
int main()
{
    int n = 3;
    int K = 3;
    cout << sum(K, n);
}

Java

// Java implementation of above approach
class GFG
{
 
// Function to return sum
static int sum(int k, int n)
{
    int sum = (int)(Math.pow(k, n + 1) -
                    Math.pow(k - 1, n + 1));
 
    return sum;
}
 
// Driver code
public static void main(String args[])
{
    int n = 3;
    int K = 3;
    System.out.print(sum(K, n));
}
}
 
// This code is contributed
// by Akanksha Rai

Python3

# Function to return sum
def sum(k, n):
    sum = (pow(k, n + 1) -
           pow(k - 1, n + 1));
 
    return sum;
 
# Driver code
n = 3;
K = 3;
print(sum(K, n));
 
# This code is contributed by mits

C#

// C# implementation of above approach
using System;
 
class GFG
{
 
// Function to return sum
static int sum(int k, int n)
{
    int sum = (int)(Math.Pow(k, n + 1) -
                    Math.Pow(k - 1, n + 1));
 
    return sum;
}
 
// Driver code
public static void Main()
{
    int n = 3;
    int K = 3;
    Console.Write(sum(K, n));
}
}
 
// This code is contributed
// by Akanksha Rai

PHP

<?php
 
// Function to return sum
function sum($k, $n)
{
    $sum = pow($k, $n + 1) -
           pow($k - 1, $n + 1);
 
    return $sum;
}
 
// Driver code
$n = 3;
$K = 3;
echo sum($K, $n);
 
// This code is contributed
// by Akanksha Rai

Javascript

<script>
// Javascript implementation of the approach
 
    // Function to return sum
    function sum(k,n)
    {
        let sum = 0;
        for (let i = 0; i <= n; i++) {
            let p = 1;
   
            for (let j = 0; j < n - i; j++) {
                p = p * k;
            }
   
            for (let j = 0; j < i; j++) {
                p = p * (k - 1);
            }
   
            sum = sum + p;
        }
        return sum;
    }
     
    // Driver code
    let n = 3;
    let K = 3;
    document.write(sum(K, n));
 
 
// This code is contributed by unknown2108
</script>
Producción: 

65

 

Complejidad temporal: O( n )

Espacio Auxiliar: O(1)

  • Tercer enfoque (eficiente): O(log n)
    Nota: La complejidad del tiempo se puede reducir aún más a O(log(n)), calculando la potencia en complejidad log(n). 
    A continuación se muestra la implementación del enfoque anterior: 

C++

#include <bits/stdc++.h>
using namespace std;
 
// Recursive C program to compute modular power
int exponent(int A, int B)
{
    // Base cases
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;
 
    // If B is even
    long y;
    if (B % 2 == 0) {
        y = exponent(A, B / 2);
        y = (y * y);
    }
 
    // If B is odd
    else {
        y = A;
        y = (y * exponent(A, B - 1));
    }
 
    return y;
}
 
// Function to return sum
int sum(int k, int n)
{
    int sum = exponent(k, n + 1)
              - exponent(k - 1, n + 1);
 
    return sum;
}
 
// Driver code
int main()
{
    int n = 3;
    int K = 3;
    cout << sum(K, n);
}

Java

import java.lang.Math;
 
class GFG
{
     
// Recursive C program to compute modular power
static int exponent(int A, int B)
{
    // Base cases
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;
 
    // If B is even
    int y;
    if (B % 2 == 0)
    {
        y = exponent(A, B / 2);
        y = (y * y);
    }
 
    // If B is odd
    else
    {
        y = A;
        y = (y * exponent(A, B - 1));
    }
 
    return y;
}
 
// Function to return sum
static int sum(int k, int n)
{
    int sum = exponent(k, n + 1)
            - exponent(k - 1, n + 1);
 
    return sum;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 3;
    int K = 3;
    System.out.println(sum(K, n));
}
}
 
// This code is contributed by Code_Mech.

Python3

# Recursive python3 program to compute modular power
 
def exponent(A, B):
    # Base cases
    if (A == 0):
        return 0;
    if (B == 0):
        return 1;
 
    # If B is even
    if (B % 2 == 0):
        y = exponent(A, B / 2);
        y = (y * y);
 
    # If B is odd
    else:
        y = A;
        y = (y * exponent(A, B - 1));
 
    return y;
 
# Function to return sum
def sum(k, n):
    sum = exponent(k, n + 1) - exponent(k - 1, n + 1);
 
    return sum;
 
# Driver code
n = 3;
K = 3;
print(sum(K, n));
 
# This code has been contributed by 29AjayKumar

C#

// C# program of above approach
using System;
 
class GFG
{
     
// Recursive C program to compute modular power
static int exponent(int A, int B)
{
    // Base cases
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;
 
    // If B is even
    int y;
    if (B % 2 == 0)
    {
        y = exponent(A, B / 2);
        y = (y * y);
    }
 
    // If B is odd
    else
    {
        y = A;
        y = (y * exponent(A, B - 1));
    }
 
    return y;
}
 
// Function to return sum
static int sum(int k, int n)
{
    int sum = exponent(k, n + 1)
            - exponent(k - 1, n + 1);
 
    return sum;
}
 
// Driver code
public static void Main()
{
    int n = 3;
    int K = 3;
    Console.WriteLine(sum(K, n));
}
}
 
// This code is contributed by Code_Mech.

PHP

<?php
// Recursive C program to compute modular power
 
function exponent($A, $B)
{
    // Base cases
    if ($A == 0)
        return 0;
    if ($B == 0)
        return 1;
 
    // If B is even
    if ($B % 2 == 0)
    {
        $y = exponent($A, $B / 2);
        $y = ($y * $y);
    }
 
    // If B is odd
    else
    {
        $y = $A;
        $y = ($y * exponent($A, $B - 1));
    }
 
    return $y;
}
 
// Function to return sum
function sum($k, $n)
{
    $sum = exponent($k, $n + 1) -
           exponent($k - 1, $n + 1);
 
    return $sum;
}
 
// Driver code
$n = 3;
$K = 3;
echo sum($K, $n);
 
// This code is contributed by Akanksha Rai
?>

Javascript

<script>
 
// Recursive Javascript program to
// compute modular power
function exponent(A, B)
{
     
    // Base cases
    if (A == 0)
        return 0;
    if (B == 0)
        return 1;
 
    // If B is even
    let y;
    if (B % 2 == 0)
    {
        y = exponent(A, parseInt(B / 2, 10));
        y = (y * y);
    }
 
    // If B is odd
    else
    {
        y = A;
        y = (y * exponent(A, B - 1));
    }
    return y;
}
 
// Function to return sum
function sum(k, n)
{
    let sum = exponent(k, n + 1) -
              exponent(k - 1, n + 1);
 
    return sum;
}
 
// Driver code
let n = 3;
let K = 3;
 
document.write(sum(K, n));
 
// This code is contributed by divyeshrabadiya07  
 
</script>
Producción: 

65

 

Complejidad de tiempo: O (logn)

Espacio auxiliar: O (logn)

Publicación traducida automáticamente

Artículo escrito por skc161931 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 *