Dado un número n y un valor k , la tarea es encontrar el m más pequeño ( m>=n), tal que m pueda representarse como una suma de distintas potencias de k.
Ejemplos:
Entrada: n = 5, k = 5
Salida: 5
Explicación: 5 = 5 1Entrada: n = 29, k = 5
Salida: 30
Explicación: 30 = 5 1 + 5 2
Acercarse:
- Almacene la representación k-nary(base k) de n. Luego recorra cada elemento de la representación base k.
- Si la representación en base k de esta posición es 1 o 0, entonces continúe. Si es >1, significa que la potencia actual de k ocurre más de una vez.
- En ese caso, esa potencia se suma k (valor de posición de k) veces, lo que la convierte en una potencia más (((k-1)+1).k x = kk x = k x+1 ).
- Dado que se debe encontrar el número más pequeño, después de este paso, todas las potencias inferiores de k se reducen a 0, ya que la adición de (kb)k x (b=valor en esa posición en la representación base k) ya ha hecho que el mayor que el número anterior.
- Finalmente, vuelva a convertir el número a la forma decimal.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
// Function to find the smallest number
// greater than or equal to n represented
// as the sum of distinct powers of k
void greaterK(ll n, ll k)
{
// Vector P to store the base k
// representation of the number
vector<ll> p;
ll x = n;
while (x) {
p.pb(x % k);
x /= k;
}
int idx = 0;
for (ll i = 0; i < (ll)p.size() - 1; ++i) {
if (p[i] >= 2) {
// If the representation is >=2, then
// this power of k has to be added
// once again and then increase the
// next power of k and make the
// current power 0
p[i] = 0;
p[i + 1]++;
// Reduce all the lower power of
// k to 0
for (int j = idx; j < i; ++j) {
p[j] = 0;
}
idx = i + 1;
}
if (p[i] == k) {
p[i] = 0;
p[i + 1]++;
}
}
ll j = (ll)p.size() - 1;
// Check if the most significant
// bit also satisfy the above
// conditions
if (p[j] >= 2) {
for (auto& i : p)
i = 0;
p.pb(1);
}
ll ans = 0;
// Converting back from the
// k-nary representation to
// decimal form.
for (ll i = p.size() - 1; i >= 0; --i) {
ans = ans * k + p[i];
}
cout << ans << endl;
}
int main()
{
ll n = 29, k = 7;
greaterK(n, k);
return 0;
}
Java
// Java implementation of the above approach
class GFG{
// Function to find the smallest number
// greater than or equal to n represented
// as the sum of distinct powers of k
static void greaterK(int n, int k)
{
// Vector P to store the base k
// representation of the number
int []p = new int[String.valueOf(n).length() + 2];
int index = 0;
int x = n;
while (x > 0)
{
p[index]=(int) (x % k);
x /= k;
index++;
}
int idx = 0;
for (int i = 0; i < p.length - 1; ++i)
{
if (p[i] >= 2)
{
// If the representation is >=2, then
// this power of k has to be added
// once again and then increase the
// next power of k and make the
// current power 0
p[i] = 0;
p[i + 1]++;
// Reduce all the lower power of
// k to 0
for (int j = idx; j < i; ++j)
{
p[j] = 0;
}
idx = i + 1;
}
if (p[i] == k)
{
p[i] = 0;
p[i + 1]++;
}
}
int j = p.length - 1;
// Check if the most significant
// bit also satisfy the above
// conditions
if (p[j] >= 2)
{
p[index] = 1;
index++;
}
int ans = 0;
// Converting back from the
// k-nary representation to
// decimal form.
for (int i = p.length - 1; i >= 0; --i)
{
ans = ans * k + p[i];
}
System.out.print(ans +"\n");
}
// Driver code
public static void main(String[] args)
{
int n = 29, k = 7;
greaterK(n, k);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach # Function to find the smallest number # greater than or equal to n represented # as the sum of distinct powers of k def greaterK(n, k): # Vector P to store the base k # representation of the number index = 0 p = [0 for i in range(n + 2)] x = n while (x > 0): p[index] = x % k x //= k index += 1 idx = 0 for i in range(0,len(p)-1, 1): if (p[i] >= 2): # If the representation is >=2, then # this power of k has to be added # once again and then increase the # next power of k and make the # current power 0 p[i] = 0 p[i + 1] += 1 # Reduce all the lower power of # k to 0 for j in range(idx, i, 1): p[j] = 0 idx = i + 1 if (p[i] == k): p[i] = 0 p[i + 1] += 1 j = len(p) - 1 # Check if the most significant # bit also satisfy the above # conditions if (p[j] >= 2): p[index] = 1 index += 1 ans = 0 # Converting back from the # k-nary representation to # decimal form. i = len(p)-1 while(i>= 0): ans = ans * k + p[i] i -= 1 print(ans) if __name__ == '__main__': n = 29 k = 7 greaterK(n, k) # This code is contributed by Surendra_Gangwar
C#
// C# implementation of the above approach
using System;
class GFG{
// Function to find the smallest number
// greater than or equal to n represented
// as the sum of distinct powers of k
static void greaterK(int n, int k)
{
// List P to store the base k
// representation of the number
int []p = new int[String.Join("",n).Length + 2];
int index = 0;
int x = n;
int j;
while (x > 0)
{
p[index] = (int) (x % k);
x /= k;
index++;
}
int idx = 0;
for (int i = 0; i < p.Length - 1; ++i)
{
if (p[i] >= 2)
{
// If the representation is >=2, then
// this power of k has to be added
// once again and then increase the
// next power of k and make the
// current power 0
p[i] = 0;
p[i + 1]++;
// Reduce all the lower power of
// k to 0
for (j = idx; j < i; ++j)
{
p[j] = 0;
}
idx = i + 1;
}
if (p[i] == k)
{
p[i] = 0;
p[i + 1]++;
}
}
j = p.Length - 1;
// Check if the most significant
// bit also satisfy the above
// conditions
if (p[j] >= 2)
{
p[index] = 1;
index++;
}
int ans = 0;
// Converting back from the
// k-nary representation to
// decimal form.
for (int i = p.Length - 1; i >= 0; --i)
{
ans = ans * k + p[i];
}
Console.Write(ans +"\n");
}
// Driver code
public static void Main(String[] args)
{
int n = 29, k = 7;
greaterK(n, k);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation of the above approach
// Function to find the smallest number
// greater than or equal to n represented
// as the sum of distinct powers of k
function greaterK(n, k) {
// Vector P to store the base k
// representation of the number
let p = new Array(String(n).length + 2).fill(0);
let index = 0;
let x = n;
while (x > 0) {
p[index] = (x % k);
x = Math.floor(x / k);
index++;
}
let idx = 0;
for (let i = 0; i < p.length - 1; ++i) {
if (p[i] >= 2) {
// If the representation is >=2, then
// this power of k has to be added
// once again and then increase the
// next power of k and make the
// current power 0
p[i] = 0;
p[i + 1]++;
// Reduce all the lower power of
// k to 0
for (let j = idx; j < i; ++j) {
p[j] = 0;
}
idx = i + 1;
}
if (p[i] == k) {
p[i] = 0;
p[i + 1]++;
}
}
let j = p.length - 1;
// Check if the most significant
// bit also satisfy the above
// conditions
if (p[j] >= 2) {
p[index] = 1;
index++;
}
let ans = 0;
// Converting back from the
// k-nary representation to
// decimal form.
for (let i = p.length - 1; i >= 0; --i) {
ans = ans * k + p[i];
}
document.write(ans + "<br>");
}
// Driver code
let n = 29, k = 7;
greaterK(n, k);
// This code is contributed by gfgking
</script>
Producción:
49
Complejidad de tiempo: O (log k n)
Espacio Auxiliar: O(log k n)
Publicación traducida automáticamente
Artículo escrito por little_angel y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA