Given a value K and n, the task is to find the sum of the below series:
Kn + ( K(n-1) * (K-1)1 ) + ( K(n-2) * (K-1)2 ) + ……. (K-1)n
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(n2)
- Total number of term in series = n+1
- 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 sumint sum(int k, int n){ int sum = pow(k, n + 1) - pow(k - 1, n + 1); return sum;}// Driver codeint main(){ int n = 3; int K = 3; cout << sum(K, n);} |
Java
// Java implementation of above approachclass GFG{// Function to return sumstatic int sum(int k, int n){ int sum = (int)(Math.pow(k, n + 1) - Math.pow(k - 1, n + 1)); return sum;}// Driver codepublic 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 approachusing System;class GFG{// Function to return sumstatic int sum(int k, int n){ int sum = (int)(Math.Pow(k, n + 1) - Math.Pow(k - 1, n + 1)); return sum;}// Driver codepublic 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 sumfunction 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:
65
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 powerint 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 sumint sum(int k, int n){ int sum = exponent(k, n + 1) - exponent(k - 1, n + 1); return sum;}// Driver codeint main(){ int n = 3; int K = 3; cout << sum(K, n);} |
Java
import java.lang.Math;class GFG{ // Recursive C program to compute modular powerstatic 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 sumstatic int sum(int k, int n){ int sum = exponent(k, n + 1) - exponent(k - 1, n + 1); return sum;}// Driver codepublic 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 powerdef 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 sumdef sum(k, n): sum = exponent(k, n + 1) - exponent(k - 1, n + 1); return sum;# Driver coden = 3;K = 3;print(sum(K, n));# This code has been contributed by 29AjayKumar |
C#
// C# program of above approachusing System;class GFG{ // Recursive C program to compute modular powerstatic 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 sumstatic int sum(int k, int n){ int sum = exponent(k, n + 1) - exponent(k - 1, n + 1); return sum;}// Driver codepublic 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 powerfunction 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 sumfunction 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 powerfunction 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 sumfunction sum(k, n){ let sum = exponent(k, n + 1) - exponent(k - 1, n + 1); return sum;}// Driver codelet n = 3;let K = 3;document.write(sum(K, n));// This code is contributed by divyeshrabadiya07 </script> |
Output:
65
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
