Represent K^N as the sum of exactly N numbers
Given two numbers N and K, the task is to represent KN as the sum of exactly N numbers. Print NA if no such numbers are possible.
Examples:
Input: N = 5, K = 2
Output: 2 2 4 8 16
Explanation:
2 + 2 + 4 + 8 + 16 = 32 = 25
Input: N = 4, K = 3
Output: 3 6 18 54
Explanation:
3 + 6 + 18 + 54 = 81 = 34
Approach: In order to obtain numbers such that their sum is a power of K, we can choose the numbers that follow the condition:
This will always give the sum as a power of K.
For example: This can be illustrated as:
Let N = 3 and K = 4. We need to represent 43 (=64) as the sum of exactly 3 numbers According to the mentioned approach, The 3 numbers which can be chosen are (41) = 4 (42 - 41) = 16 - 4 = 12 (43 - 42) = 64 - 16 = 48 Adding the numbers = 4 + 12 + 48 = 64 which is clearly 43 Therefore the required 3 numbers are 4, 12 and 48.
Below is the implementation of the above approach:
C++
// C++ program to represent K^N // as the sum of exactly N numbers #include <bits/stdc++.h> #define ll long long int using namespace std; // Function to print N numbers whose // sum is a power of K void print(ll n, ll k) { // Printing K ^ 1 cout << k << " " ; // Loop to print the difference of // powers from K ^ 2 for ( int i = 2; i <= n; i++) { ll x = pow (k, i) - pow (k, i - 1); cout << x << " " ; } } // Driver code int main() { ll N = 3, K = 4; print(N, K); return 0; } |
Java
// Java program to represent K^N // as the sum of exactly N numbers import java.util.*; class GFG{ // Function to print N numbers whose // sum is a power of K static void print( int n, int k) { // Printing K ^ 1 System.out.print(k+ " " ); // Loop to print the difference of // powers from K ^ 2 for ( int i = 2 ; i <= n; i++) { int x = ( int ) (Math.pow(k, i) - Math.pow(k, i - 1 )); System.out.print(x+ " " ); } } // Driver code public static void main(String[] args) { int N = 3 , K = 4 ; print(N, K); } } // This code is contributed by 29AjayKumar |
Python 3
# Python 3 program to represent K^N # as the sum of exactly N numbers from math import pow # Function to print N numbers whose # sum is a power of K def printf(n, k): # Printing K ^ 1 print ( int (k),end = " " ) # Loop to print the difference of # powers from K ^ 2 for i in range ( 2 , n + 1 , 1 ): x = pow (k, i) - pow (k, i - 1 ) print ( int (x),end = " " ) # Driver code if __name__ = = '__main__' : N = 3 K = 4 printf(N, K) # This code is contributed by Surendra_Gangwar |
C#
// C# program to represent K^N // as the sum of exactly N numbers using System; class GFG{ // Function to print N numbers whose // sum is a power of K static void print( int n, int k) { // Printing K ^ 1 Console.Write(k+ " " ); // Loop to print the difference of // powers from K ^ 2 for ( int i = 2; i <= n; i++) { int x = ( int ) (Math.Pow(k, i) - Math.Pow(k, i - 1)); Console.Write(x+ " " ); } } // Driver code public static void Main(String[] args) { int N = 3, K = 4; print(N, K); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to represent K^N // as the sum of exactly N numbers // Function to print N numbers whose // sum is a power of K function print(n, k) { // Printing K ^ 1 document.write( k + " " ); // Loop to print the difference of // powers from K ^ 2 for ( var i = 2; i <= n; i++) { var x = Math.pow(k, i) - Math.pow(k, i - 1); document.write( x + " " ); } } // Driver code var N = 3, K = 4; print(N, K); // This code is contributed by rutvik_56. </script> |
Output:
4 12 48
Time Complexity: O(n)
Auxiliary Space: O(1)