Suma de cocientes de división de N por potencias de K que no exceda N

Dados dos números enteros positivos N y K , la tarea es encontrar la suma de los cocientes de la división de N entre potencias de K menores o iguales que N .

Ejemplos:

Entrada: N = 10, K = 2
Salida: 18
Explicación:
Dividir 10 por 1 (= 2 ⁰ ). Cociente = 10. Por lo tanto, suma = 10. 
Dividiendo 10 por 2 (= 2 ¹ ). Cociente = 5. Por lo tanto, suma = 15. 
Divide 10 entre 4 (= 2 ² ). Cociente = 2. Por lo tanto, suma = 17. 
Divide 10 entre 8 (= 2 ³ ). Cociente = 1. Por lo tanto, suma = 18. 

Entrada: N = 5, K=2
Salida: 8
Explicación:
Dividir 5 por 1 (= 2 ⁰ ). Cociente = 5. Por lo tanto, suma = 5. 
Divide 5 entre 2 (= 2 ¹ ). Cociente = 2. Por lo tanto, suma = 7. 
Divide 5 entre 4 (= 2 ² ). Cociente = 1. Por lo tanto, suma = 8. 

Planteamiento: La idea es iterar un ciclo mientras la potencia actual de K es menor o igual a N y seguir sumando el cociente a la suma en cada iteración.
Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos sum , para almacenar la suma requerida.
• Inicialice una variable, digamos i = 1 (= K ⁰ ) para almacenar las potencias de K .
• Iterar hasta el valor de i ≤ N y realizar las siguientes operaciones:
  • Almacena el cociente obtenido al dividir N entre i en una variable, digamos X .
  • Sume el valor de X a ans y multiplique i por K para obtener la siguiente potencia de K.
• Imprime el valor de la suma como resultado.

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 calculate sum of
// quotients obtained by dividing
// N by powers of K <= N
int findSum(int N, int K)
{
    // Store the required sum
    int ans = 0;
    int i = 1;
 
    // Iterate until i exceeds N
    while (i <= N) {
 
        // Update sum
        ans += N / i;
 
        // Multiply i by K to
        // obtain next power of K
        i = i * K;
    }
 
    // Print the result
    cout << ans;
}
 
// Driver Code
int main()
{
    // Given N and K
    int N = 10, K = 2;
    findSum(N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
  // Function to calculate sum of
  // quotients obtained by dividing
  // N by powers of K <= N
  static void findSum(int N, int K)
  {
 
    // Store the required sum
    int ans = 0;
    int i = 1;
 
    // Iterate until i exceeds N
    while (i <= N)
    {
 
      // Update sum
      ans += N / i;
 
      // Multiply i by K to
      // obtain next power of K
      i = i * K;
    }
 
    // Print the result
    System.out.println(ans);
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    // Given N and K
    int N = 10, K = 2;
    findSum(N, K);
  }
}
 
// This code is contributed by shubhamsingh10

# Python3 program for the above approach
 
# Function to calculate sum of
# quotients obtained by dividing
# N by powers of K <= N
def findSum(N, K):
   
    # Store the required sum
    ans = 0
    i = 1
 
    # Iterate until i exceeds N
    while (i <= N):
 
        # Update sum
        ans += N // i
 
        # Multiply i by K to
        # obtain next power of K
        i = i * K
 
    # Print the result
    print (ans)
 
# Driver Code
if __name__ == '__main__':
   
    # Given N and K
    N, K = 10, 2
    findSum(N, K)
 
    # This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
 
class GFG{
     
// Function to calculate sum of
// quotients obtained by dividing
// N by powers of K <= N
static void findSum(int N, int K)
{
 
    // Store the required sum
    int ans = 0;
    int i = 1;
     
    // Iterate until i exceeds N
    while (i <= N)
    {
         
        // Update sum
        ans += N / i;
         
        // Multiply i by K to
        // obtain next power of K
        i = i * K;
    }
     
    // Print the result
    Console.Write(ans);
}
 
// Driver code
static void Main()
{
     
    // Given N and K
    int N = 10, K = 2;
     
    findSum(N, K);
}
}
 
// This code is contributed by code_hunt

<script>
 
// javascript program for the above approach
 
// Function to calculate sum of
// quotients obtained by dividing
// N by powers of K <= N
function findSum(N, K)
{
    // Store the required sum
    var ans = 0;
    var i = 1;
 
    // Iterate until i exceeds N
    while (i <= N) {
 
        // Update sum
        ans += Math.floor(N / i);
 
        // Multiply i by K to
        // obtain next power of K
        i = i * K;
    }
 
    // Print the result
    document.write(ans);
}
 
// Driver Code
 
    // Given N and K
    var N = 10, K = 2;
    findSum(N, K);
     
</script>

18

Complejidad temporal: O(log _K (N))
Espacio auxiliar: O(1)