Encuentre el K-ésimo número que se puede escribir como suma de diferentes potencias de N

Dados dos números enteros positivos N y K . La tarea es encontrar el número K-ésimo que se puede escribir como la suma de diferentes potencias no negativas de  N.

Ejemplos:

Entrada: N = 3, K = 4
Salida: 9
Explicación:
El primer número que se puede escribir como suma de potencias de 3 es [1 = 3 ⁰ ] El
segundo número que se puede escribir como suma de potencias de 3 es [3 = 3 ¹ ]
El tercer número que se puede escribir como suma de potencias de 3 es [4 = 3 ⁰ + 3 ¹ ] El
cuarto número que se puede escribir como suma de potencias de 3 es [9 = 3 ² ]
Por lo tanto, la respuesta es 9.

Entrada: N= 2, K = 12
Salida: 12

Enfoque: este problema se puede resolver utilizando el concepto de conversión de decimal a binario . La idea es encontrar la representación binaria de K y comenzar a iterar desde el bit menos significativo hasta el bit más significativo. Si el bit actual está configurado, incluya la potencia correspondiente de N en la respuesta; de lo contrario, omita ese bit. Consulte la imagen a continuación para una mejor comprensión.

Ejemplo: Cuando N = 3, K = 9

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find Kth number that can be
// represented as sum of different
// non-negative powers of N
int FindKthNum(int n, int k)
{
    // To store the ans
    int ans = 0;
 
    // Value of current power of N
    int currPowOfN = 1;
 
    // Iterating through bits of K
    // from LSB to MSB
    while (k) {
        // If the current bit is 1 then include
        // corresponding power of n into ans
        if (k & 1) {
            ans = ans + currPowOfN;
        }
 
        currPowOfN = currPowOfN * n;
        k = k / 2;
    }
 
    // Return the result
    return ans;
}
 
// Driver Code
int main()
{
    int N = 3;
    int K = 4;
 
    cout << FindKthNum(N, K);
}

// Java program for the above approach
class GFG
{
   
  // Function to find Kth number that can be
  // represented as sum of different
  // non-negative powers of N
  static int FindKthNum(int n, int k)
  {
     
      // To store the ans
      int ans = 0;
 
      // Value of current power of N
      int currPowOfN = 1;
 
      // Iterating through bits of K
      // from LSB to MSB
      while (k > 0)
      {
         
          // If the current bit is 1 then include
          // corresponding power of n into ans
          if ((k & 1) == 1) {
              ans = ans + currPowOfN;
          }
 
          currPowOfN = currPowOfN * n;
          k = k / 2;
      }
 
      // Return the result
      return ans;
  }
  
  // Driver Code
  public static void main(String []args)
  {
      int N = 3;
      int K = 4;
 
      System.out.println(FindKthNum(N, K));
  }
 
}
 
// This Code is contributed by ihritik

# Python program for the above approach
 
# Function to find Kth number that can be
# represented as sum of different
# non-negative powers of N
def FindKthNum(n, k):
 
  # To store the ans
  ans = 0
 
  # value of current power of N
  currPowOfN = 1
 
  # Iterating through bits of K
  # from LSB to MSB
  while (k > 0):
     
    # If the current bit is 1 then include
    # corresponding power of n into ans
    if ((k & 1) == 1) :
      ans = ans + currPowOfN
     
 
    currPowOfN = currPowOfN * n
    k = k // 2
   
 
  # Return the result
  return ans
 
 
 
# Driver Code
 
N = 3
K = 4
print(FindKthNum(N, K));
   
 
# This Code is contributed by ihritik

// C# program for the above approach
using System;
class GFG
{
   
  // Function to find Kth number that can be
  // represented as sum of different
  // non-negative powers of N
  static int FindKthNum(int n, int k)
  {
     
      // To store the ans
      int ans = 0;
 
      // Value of current power of N
      int currPowOfN = 1;
 
      // Iterating through bits of K
      // from LSB to MSB
      while (k > 0)
      {
         
          // If the current bit is 1 then include
          // corresponding power of n into ans
          if ((k & 1) == 1) {
              ans = ans + currPowOfN;
          }
 
          currPowOfN = currPowOfN * n;
          k = k / 2;
      }
 
      // Return the result
      return ans;
  }
  
 
  // Driver Code
  public static void Main()
  {
      int N = 3;
      int K = 4;
 
      Console.WriteLine(FindKthNum(N, K));
  }
 
}
 
// This Code is contributed by ihritik

<script>
// JavaScript program for the above approach
 
// Function to find Kth number that can be
// represented as sum of different
// non-negative powers of N
function FindKthNum(n, k)
{
 
    // To store the ans
    let ans = 0;
 
    // Value of current power of N
    let currPowOfN = 1;
 
    // Iterating through bits of K
    // from LSB to MSB
    while (k)
    {
     
        // If the current bit is 1 then include
        // corresponding power of n into ans
        if (k & 1)
        {
            ans = ans + currPowOfN;
        }
 
        currPowOfN = currPowOfN * n;
        k = Math.floor(k / 2);
    }
 
    // Return the result
    return ans;
}
 
// Driver Code
let N = 3;
let K = 4;
document.write(FindKthNum(N, K));
 
// This code is contributed by rohitsingh07052.
</script>

9

Complejidad de tiempo: O (log ₂ K)

Complejidad espacial: O(1)