Dados dos números N y K , la tarea es imprimir las distintas potencias de N que se utilizan para obtener la suma K . Si no es posible, imprima -1 .
Ejemplos:
Entrada: N = 3, K = 40
Salida: 0, 1, 2, 3
Explicación:
El valor de N es 3.
3 0 + 3 1 + 3 2 + 3 3 = 40Entrada: N = 4, K = 65
Salida: 0, 3
El valor de N es 4.
4 0 + 4 3 = 65Entrada: N = 4, K = 18
Salida: -1
Explicación:
Es imposible obtener 18 sumando la potencia de 4.
Observación: Una observación que debe hacerse para cualquier número arbitrario a es que no puede existir un número mayor que a K si todas las potencias de a desde 0 hasta k-1 se suman usando cada potencia como máximo una vez.
Ejemplo: Sea a = 3 y K = 4. Entonces:
3 4 = 81.
3 0 + 3 1 + 3 2 + 3 3 = 40 que es menor que 81(3 4 ).
Enfoque ingenuo: al usar la observación anterior, se puede formar el enfoque ingenuo. La idea es restar continuamente la potencia más alta de N que no exceda K de K hasta que K llegue a 0. Si en cualquier caso, K se vuelve igual a alguna potencia que ya se le restó anteriormente, entonces no es posible obtener la suma igual a K. Por lo tanto, se utiliza una array para realizar un seguimiento de las potencias que se han restado de K.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find distinct
// powers of N that add upto K
#include <bits/stdc++.h>
using namespace std;
// Function to return the highest power
// of N not exceeding K
int highestPower(int n, int k)
{
int i = 0;
int a = pow(n, i);
// Loop to find the highest power
// less than K
while (a <= k) {
i += 1;
a = pow(n, i);
}
return i - 1;
}
// Initializing the PowerArray
// with all 0's.
int b[50] = { 0 };
// Function to print
// the distinct powers of N
// that add upto K
int PowerArray(int n, int k)
{
while (k) {
// Getting the highest
// power of n before k
int t = highestPower(n, k);
// To check if the power
// is being used twice or not
if (b[t]) {
// Print -1 if power
// is being used twice
cout << -1;
return 0;
}
else
// If the power is not visited,
// then mark the power as visited
b[t] = 1;
// Decrementing the value of K
k -= pow(n, t);
}
// Printing the powers of N
// that sum up to K
for (int i = 0; i < 50; i++) {
if (b[i]) {
cout << i << ", ";
}
}
}
// Driver code
int main()
{
int N = 3;
int K = 40;
PowerArray(N, K);
return 0;
}
Java
// Java implementation to find distinct
// powers of N that add upto K
class GFG{
// Function to return the highest power
// of N not exceeding K
static int highestPower(int n, int k)
{
int i = 0;
int a = (int) Math.pow(n, i);
// Loop to find the highest power
// less than K
while (a <= k) {
i += 1;
a = (int) Math.pow(n, i);
}
return i - 1;
}
// Initializing the PowerArray
// with all 0's.
static int b[] = new int[50];
// Function to print
// the distinct powers of N
// that add upto K
static int PowerArray(int n, int k)
{
while (k>0) {
// Getting the highest
// power of n before k
int t = highestPower(n, k);
// To check if the power
// is being used twice or not
if (b[t]>0) {
// Print -1 if power
// is being used twice
System.out.print(-1);
return 0;
}
else
// If the power is not visited,
// then mark the power as visited
b[t] = 1;
// Decrementing the value of K
k -= Math.pow(n, t);
}
// Printing the powers of N
// that sum up to K
for (int i = 0; i < 50; i++) {
if (b[i] > 0) {
System.out.print(i+ ", ");
}
}
return 0;
}
// Driver code
public static void main(String[] args)
{
int N = 3;
int K = 40;
PowerArray(N, K);
}
}
// This code contributed by Rajput-Ji
Python3
# Python 3 implementation to find distinct # powers of N that add up to K from math import pow # Function to return the highest power # of N not exceeding K def highestPower(n,k): i = 0 a = pow(n, i) # Loop to find the highest power # less than K while (a <= k): i += 1 a = pow(n, i) return i - 1 # Initializing the PowerArray # with all 0's. b = [0 for i in range(50)] # Function to print # the distinct powers of N # that add upto K def PowerArray(n, k): while (k): # Getting the highest # power of n before k t = highestPower(n, k) # To check if the power # is being used twice or not if (b[t]): # Print -1 if power # is being used twice print(-1) return 0 else: # If the power is not visited, # then mark the power as visited b[t] = 1 # Decrementing the value of K k -= pow(n, t) # Printing the powers of N # that sum up to K for i in range(50): if (b[i]): print(i,end = ', ') # Driver code if __name__ == '__main__': N = 3 K = 40 PowerArray(N, K) # This code is contributed by Surendra_Gangwar
C#
// C# implementation to find distinct
// powers of N that add up to K
using System;
public class GFG{
// Function to return the highest power
// of N not exceeding K
static int highestPower(int n, int k)
{
int i = 0;
int a = (int) Math.Pow(n, i);
// Loop to find the highest power
// less than K
while (a <= k) {
i += 1;
a = (int) Math.Pow(n, i);
}
return i - 1;
}
// Initializing the PowerArray
// with all 0's.
static int []b = new int[50];
// Function to print
// the distinct powers of N
// that add upto K
static int PowerArray(int n, int k)
{
while (k > 0) {
// Getting the highest
// power of n before k
int t = highestPower(n, k);
// To check if the power
// is being used twice or not
if (b[t] > 0) {
// Print -1 if power
// is being used twice
Console.Write(-1);
return 0;
}
else
// If the power is not visited,
// then mark the power as visited
b[t] = 1;
// Decrementing the value of K
k -= (int)Math.Pow(n, t);
}
// Printing the powers of N
// that sum up to K
for (int i = 0; i < 50; i++) {
if (b[i] > 0) {
Console.Write(i+ ", ");
}
}
return 0;
}
// Driver code
public static void Main(String[] args)
{
int N = 3;
int K = 40;
PowerArray(N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation to find distinct
// powers of N that add upto K
// Function to return the highest power
// of N not exceeding K
function highestPower(n, k)
{
let i = 0;
let a = Math.pow(n, i);
// Loop to find the highest power
// less than K
while (a <= k) {
i += 1;
a = Math.pow(n, i);
}
return i - 1;
}
// Initializing the PowerArray
// with all 0's.
let b = Array.from({length: 50}, (_, i) => 0);
// Function to print
// the distinct powers of N
// that add upto K
function PowerArray(n, k)
{
while (k>0) {
// Getting the highest
// power of n before k
let t = highestPower(n, k);
// To check if the power
// is being used twice or not
if (b[t]>0) {
// Print -1 if power
// is being used twice
document.write(-1);
return 0;
}
else
// If the power is not visited,
// then mark the power as visited
b[t] = 1;
// Decrementing the value of K
k -= Math.pow(n, t);
}
// Printing the powers of N
// that sum up to K
for (let i = 0; i < 50; i++) {
if (b[i] > 0) {
document.write(i+ ", ");
}
}
return 0;
}
// Driver Code
let N = 3;
let K = 40;
PowerArray(N, K);
</script>
Producción:
0, 1, 2, 3,
Complejidad de tiempo: O((log N) 2 )
- El tiempo necesario para averiguar la potencia es Log(N) .
- Además de eso, se está utilizando otro bucle Log(N) para K .
- Entonces, la complejidad temporal general es Log(N) 2
Espacio Auxiliar: O(50)
Enfoque eficiente: otra observación que se puede hacer es que para que K sea la suma de las potencias de N que se pueden usar solo una vez, K % N tiene que ser 1 o 0 (1 debido a N 0 ). Por lo tanto, si ( K % N ) resulta algo distinto de 0 o 1, se puede concluir que es imposible obtener la suma K .
Por lo tanto, al usar las observaciones anteriores, se pueden seguir los siguientes pasos para calcular la respuesta:
- Primero, un contador se inicializa con 0.
- Si (K % N) = 0 , el contador se incrementa en 1 y K se actualiza a K/N .
- Si K % N = 1 , entonces la array de frecuencias f[count] se incrementa en 1 y K se actualiza a K – 1 .
- Si, en algún momento, esta f[cuenta] se convierte en más de 1, entonces devuelve -1 (porque la misma potencia no se puede usar dos veces).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find out
// the powers of N that add upto K
#include <bits/stdc++.h>
using namespace std;
// Initializing the PowerArray
// with all 0's
int b[50] = { 0 };
// Function to find the powers of N
// that add up to K
int PowerArray(int n, int k)
{
// Initializing the counter
int count = 0;
// Executing the while
// loop until K is
// greater than 0
while (k) {
if (k % n == 0) {
k /= n;
count++;
}
// If K % N == 1,
// then the power array
// is incremented by 1
else if (k % n == 1) {
k -= 1;
b[count]++;
// Checking if any power is
// occurred more than once
if (b[count] > 1) {
cout << -1;
return 0;
}
}
// For any other value, the sum of
// powers cannot be added up to K
else {
cout << -1;
return 0;
}
}
// Printing the powers of N
// that sum up to K
for (int i = 0; i < 50; i++) {
if (b[i]) {
cout << i << ", ";
}
}
}
// Driver code
int main()
{
int N = 3;
int K = 40;
PowerArray(N, K);
return 0;
}
Java
// Java implementation to find out
// the powers of N that add upto K
class GFG{
// Initializing the PowerArray
// with all 0's
static int b[] = new int[50];
// Function to find the powers of N
// that add up to K
static int PowerArray(int n, int k)
{
// Initializing the counter
int count = 0;
// Executing the while
// loop until K is
// greater than 0
while (k > 0)
{
if (k % n == 0)
{
k /= n;
count++;
}
// If K % N == 1,
// then the power array
// is incremented by 1
else if (k % n == 1)
{
k -= 1;
b[count]++;
// Checking if any power is
// occurred more than once
if (b[count] > 1)
{
System.out.print(-1);
return 0;
}
}
// For any other value, the sum of
// powers cannot be added up to K
else
{
System.out.print(-1);
return 0;
}
}
// Printing the powers of N
// that sum up to K
for(int i = 0; i < 50; i++)
{
if (b[i] != 0)
{
System.out.print(i + ", ");
}
}
return Integer.MIN_VALUE;
}
// Driver code
public static void main(String[] args)
{
int N = 3;
int K = 40;
PowerArray(N, K);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to find out # the powers of N that add upto K # Initializing the PowerArray # with all 0's b = [0 for i in range(50)] # Function to find the powers of N # that add up to K def PowerArray(n, k): # Initializing the counter count = 0 # Executing the while # loop until K is # greater than 0 while (k): if (k % n == 0): k //= n count += 1 # If K % N == 1, # then the power array # is incremented by 1 elif (k % n == 1): k -= 1 b[count] += 1 # Checking if any power is # occurred more than once if (b[count] > 1): print(-1) return 0 # For any other value, the sum of # powers cannot be added up to K else: print(-1) return 0 # Printing the powers of N # that sum up to K for i in range(50): if (b[i]): print(i,end = ",") # Driver code if __name__ == '__main__': N = 3 K = 40 PowerArray(N, K) # This code is contributed by ipg2016107
C#
// C# implementation to find out
// the powers of N that add upto K
using System;
class GFG{
// Initializing the PowerArray
// with all 0's
static int []b = new int[50];
// Function to find the powers of N
// that add up to K
static int PowerArray(int n, int k)
{
// Initializing the counter
int count = 0;
// Executing the while loop
// until K is greater than 0
while (k > 0)
{
if (k % n == 0)
{
k /= n;
count++;
}
// If K % N == 1, then
// the power array is
// incremented by 1
else if (k % n == 1)
{
k -= 1;
b[count]++;
// Checking if any power is
// occurred more than once
if (b[count] > 1)
{
Console.Write(-1);
return 0;
}
}
// For any other value, the sum of
// powers cannot be added up to K
else
{
Console.Write(-1);
return 0;
}
}
// Printing the powers of N
// that sum up to K
for(int i = 0; i < 50; i++)
{
if (b[i] != 0)
{
Console.Write(i + ", ");
}
}
return int.MinValue;
}
// Driver code
public static void Main(String[] args)
{
int N = 3;
int K = 40;
PowerArray(N, K);
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript implementation to find out
// the powers of N that add upto K
// Initializing the PowerArray
// with all 0's
let b = new Array(50);
b.fill(0);
// Function to find the powers of N
// that add up to K
function PowerArray(n, k)
{
// Initializing the counter
let count = 0;
// Executing the while loop
// until K is greater than 0
while (k > 0)
{
if (k % n == 0)
{
k = parseInt(k / n, 10);
count++;
}
// If K % N == 1, then
// the power array is
// incremented by 1
else if (k % n == 1)
{
k -= 1;
b[count]++;
// Checking if any power is
// occurred more than once
if (b[count] > 1)
{
document.write(-1);
return 0;
}
}
// For any other value, the sum of
// powers cannot be added up to K
else
{
document.write(-1);
return 0;
}
}
// Printing the powers of N
// that sum up to K
for(let i = 0; i < 50; i++)
{
if (b[i] != 0)
{
document.write(i + ", ");
}
}
return Number.MIN_VALUE;
}
let N = 3;
let K = 40;
PowerArray(N, K);
</script>
Producción:
0, 1, 2, 3,
Complejidad de tiempo: dado que la potencia más alta no se verifica cada vez, el tiempo de ejecución de este algoritmo es log(N) .
Espacio Auxiliar: O(50)
Publicación traducida automáticamente
Artículo escrito por snape_here y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA