Sum of the series Kn + ( K(n-1) * (K-1)1 ) + ( K(n-2) * (K-1)2 ) + ……. (K-1)n

0 0 6 minutes read

Given a value K and n, the task is to find the sum of the below series:

Kⁿ + ( K^(n-1) * (K-1)¹ ) + ( K^(n-2) * (K-1)² ) + ……. (K-1)ⁿ

Examples:

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

Simple Approach: O(n²)
1. Total number of term in series = n+1
2. Calculate each term separately, and add them:
Second Approach: O(n)
It is observed that, given series is Geometric Progression, with common ratio = (K – 1)/K
So, above expression can be simplified as:

Below is the implementation of the above approach:

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>

Output:

Time Complexity: O( n )

Auxiliary Space: O(1)

Third Approach (Efficient): O(log n)
Note: Time complexity can further be reduced to O(log(n)), by calculating power in log(n) complexity.
Below is the implementation of the above approach:

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>

Output:

Time Complexity: O(logn)

Auxiliary Space: O(logn)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!