Encuentre el número mínimo que debe agregarse a N para convertirlo en una potencia de K

Dados dos números enteros positivos N y K , la tarea es encontrar el número mínimo que se debe sumar a N para convertirlo en una potencia de K.
Ejemplos: 
 

Entrada: N = 9, K = 10 
Salida: 1 
Explicación: 
9 + 1 = 10 = 10 ¹
Entrada: N = 20, K = 5 
Salida: 5 
Explicación: 
20 + 5 = 25 = 5 ² 
 

Enfoque: La idea para resolver este problema es observar que la mínima potencia de K que se puede formar a partir de N es la siguiente potencia mayor de K. Entonces, la idea es encontrar la siguiente potencia mayor de K y encontrar la diferencia entre N y este numero La siguiente potencia mayor de K se puede encontrar mediante la fórmula, 

K ^{int(registro(N)/registro(K)) + 1}

 
Por lo tanto, el número mínimo a sumar se puede calcular mediante: 
 

Número mínimo = K ^{int(log(N)/log(K)) + 1} – N 
 

A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to find the minimum number
// to be added to N to make it a power of K
 
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to return the minimum number
// to be added to N to make it a power of K.
int minNum(int n, int k)
{
    int x = (int)(log(n) / log(k)) + 1;
 
    // Computing the difference between
    // then next greater power of K
    // and N
    int mn = pow(k, x) - n;
    return mn;
}
 
// Driver code
int main()
{
    int n = 20, k = 5;
    cout << minNum(n, k);
    return 0;
}

// Java program to find the minimum number
// to be added to N to make it a power of K
 
class GFG{
  
// Function to return the minimum number
// to be added to N to make it a power of K.
static int minNum(int n, int k)
{
    int x = (int)(Math.log(n) / Math.log(k)) + 1;
  
    // Computing the difference between
    // then next greater power of K
    // and N
    int mn = (int) (Math.pow(k, x) - n);
    return mn;
}
  
// Driver code
public static void main(String[] args)
{
    int n = 20, k = 5;
    System.out.print(minNum(n, k));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to find the minimum number
# to be added to N to make it a power of K
import math
 
# Function to return the minimum number
# to be added to N to make it a power of K.
def minNum(n, k):
     
    x = int((math.log(n) // math.log(k))) + 1
     
    # Computing the difference between
    # then next greater power of K
    # and N
    mn = pow(k, x) - n
    return mn
     
# Driver code
if __name__=='__main__':
     
    n = 20
    k = 5
    print(minNum(n, k))
 
# This code is contributed by rutvik_56

// C# program to find the minimum number
// to be added to N to make it a power of K
using System;
class GFG{
   
// Function to return the minimum number
// to be added to N to make it a power of K.
static int minNum(int n, int k)
{
    int x = (int)(Math.Log(n) /
                  Math.Log(k)) + 1;
   
    // Computing the difference between
    // then next greater power of K
    // and N
    int mn = (int)(Math.Pow(k, x) - n);
    return mn;
}
   
// Driver code
public static void Main(string[] args)
{
    int n = 20, k = 5;
    Console.Write(minNum(n, k));
}
}
  
// This code is contributed by Ritik Bansal

<script>
 
// Javascript program to find the minimum number
// to be added to N to make it a power of K
 
// Function to return the minimum number
// to be added to N to make it a power of K.
function minNum(n, k)
{
    var x = parseInt(Math.log(n) / Math.log(k)) + 1;
 
    // Computing the difference between
    // then next greater power of K
    // and N
    var mn = Math.pow(k, x) - n;
    return mn;
}
 
// Driver code
var n = 20, k = 5;
document.write( minNum(n, k));
 
</script>

5

Complejidad de tiempo: O (log n)

Espacio Auxiliar: O(1)