Potencias distintas de un número N tales que la suma es igual a K

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 = 40

Entrada: N = 4, K = 65 
Salida: 0, 3 
El valor de N es 4. 
4 0 + 4 3 = 65

Entrada: 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:  

  1. Primero, un contador se inicializa con 0.
  2. Si (K % N) = 0 , el contador se incrementa en 1 y K se actualiza a K/N .
  3. Si K % N = 1 , entonces la array de frecuencias f[count] se incrementa en 1 y K se actualiza a K – 1 .
  4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *