Distribuya N en una secuencia que tenga grupos de tamaño K de 1, 2, 4, etc.

dado un numeroN , y un número entero K . La tarea es distribuir N en una secuencia tal que el primeroLos K números de la sucesión son 2 ⁰ , los siguientes K números son 2 ¹ , y así sucesivamente hasta que la suma de la sucesión sea como máximo N . Encuentre el tamaño más grande de la secuencia.

Ejemplos :

Entrada: N = 35, K = 5
Salida: 15
Explicación: La secuencia es 1 1 1 1 1 2 2 2 2 2 4 4 4 4 4.
La suma de la secuencia es 35.  

Entrada: N = 16, K = 3
Salida: 8
Explicación: La secuencia es 1 1 1 2 2 2 4.
La suma de la secuencia es 13, que es menor que 16 

Enfoque: siga los pasos a continuación para resolver el problema: 

• Deje que variable ans almacene la salida del programa.
• Tome un bucle de 1 a i , que calcula el tamaño de la secuencia hasta la cual K*pow(2, i) < N . Agregando K a ans y restando K*pow(2, i) de N en cada bucle.
• El tamaño de la secuencia restante se calcula sumando N/pow(2, i) a ans .

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

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the size of sequence
int get(int N, int K)
{
    int ans = 0;
    int i = 0;
 
    // Loop to calculate size of sequence
    // upto which K*pow(2, i) < N.
    while (K * pow(2, i) < N) {
        N -= (K * pow(2, i));
        i++;
        ans += K;
    }
 
    // Calculate Size of remaining sequence
    ans += N / (pow(2, i));
    return ans;
}
 
// Driver code
int main()
{
    int N, K;
    N = 35;
    K = 5;
    cout << get(N, K);
    return 0;
}

// Java code to implement the above approach
class GFG {
 
  // Function to find the size of sequence
  static int get(int N, int K)
  {
    int ans = 0;
    int i = 0;
 
    // Loop to calculate size of sequence
    // upto which K*pow(2, i) < N.
    while (K * (int)Math.pow(2, i) < N) {
      N -= (K * (int)Math.pow(2, i));
      i++;
      ans += K;
    }
 
    // Calculate Size of remaining sequence
    ans += N / (int)(Math.pow(2, i));
    return ans;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int N, K;
    N = 35;
    K = 5;
    System.out.print(get(N, K));
  }
}
 
// This code is contributed by ukasp.

# Python code to implement the above approach
 
# Function to find the size of sequence
def get (N, K):
    ans = 0;
    i = 0;
 
    # Loop to calculate size of sequence
    # upto which K*pow(2, i) < N.
    while (K * (2 ** i) < N):
        N -= (K * (2 ** i));
        i += 1
        ans += K;
 
    # Calculate Size of remaining sequence
    ans += (N // (2 ** i));
    return ans;
 
# Driver code
N = 35;
K = 5;
print(get(N, K));
 
# This code is contributed by Saurabh Jaiswal

// C# code to implement the above approach
using System;
class GFG
{
 
  // Function to find the size of sequence
  static int get(int N, int K)
  {
    int ans = 0;
    int i = 0;
 
    // Loop to calculate size of sequence
    // upto which K*pow(2, i) < N.
    while (K * (int)Math.Pow(2, i) < N) {
      N -= (K * (int)Math.Pow(2, i));
      i++;
      ans += K;
    }
 
    // Calculate Size of remaining sequence
    ans += N / (int)(Math.Pow(2, i));
    return ans;
  }
 
  // Driver code
  public static void Main()
  {
    int N, K;
    N = 35;
    K = 5;
    Console.Write(get(N, K));
  }
}
 
// This code is contributed b Samim Hossain Mondal.

<script>
    // JavaScript code to implement the above approach
 
    // Function to find the size of sequence
    const get = (N, K) => {
        let ans = 0;
        let i = 0;
 
        // Loop to calculate size of sequence
        // upto which K*pow(2, i) < N.
        while (K * Math.pow(2, i) < N) {
            N -= (K * Math.pow(2, i));
            i++;
            ans += K;
        }
 
        // Calculate Size of remaining sequence
        ans += parseInt(N / (Math.pow(2, i)));
        return ans;
    }
 
    // Driver code
 
    let N, K;
    N = 35;
    K = 5;
    document.write(get(N, K));
 
// This code is contributed by rakeshsahni
 
</script>

15

Complejidad de tiempo : O(log(N)) donde la base de log es K
Espacio auxiliar : O(1)