Números mínimos necesarios para expresar cada entero por debajo de N como una suma

Tenemos un número entero N. Necesitamos expresar N como una suma de K números enteros de modo que sumando algunos (o todos) de estos números enteros podamos obtener todos los números en el rango [1, N]. ¿Cuál es el valor mínimo de K?

Ejemplos: 

Input  : N = 7
Output : 3
Explanation : Three integers are 1, 2, 4. By adding some(or all) of these groups we can get all number in the range 1 to N. 
1; 2; 1+2=3; 4; 1+4=5; 2+4=6; 1+2+4=7

Input  : N = 32
Output : 6
Explanation : Six integers are 1, 2, 4, 8, 16, 1.

Primero resolvemos el problema de números pequeños a mano. 
n=1 : 1 
n=2 : 1, 1 
n=3 : 1, 2 
n=4 : 1, 2, 1 
n=5 : 1, 2, 2 
n=6 : 1, 2, 3 
n=7 : 1, 2, 4 
n=8 : 1, 2, 4, 1
Si examinamos esto de cerca podemos ver que si  entonces los números enteros son  . Que es solo otra forma de decir  . Ahora sabemos que  el valor mínimo de K es m. 
Ahora inspeccionamos lo que sucede con  . Porque  simplemente agregamos un nuevo número entero 1 a nuestra lista de números enteros. Date cuenta de que para cada número de podemos aumentar el entero recién agregado en 1 y esa será la lista óptima de enteros. Para verificar mire N=4 a N=7, el K mínimo no cambia; sólo el último entero se incrementa en cada paso.

Por supuesto, podemos implementar esto de forma iterativa en tiempo O(log N) (insertando potencias sucesivas de 2 en la lista y el último elemento tendrá la forma N-(2^n-1)). Pero esto es exactamente lo mismo que encontrar la longitud de la expresión binaria de N, que también se puede hacer en tiempo O (log N) .

// CPP program to find count of integers needed
// to express all numbers from 1 to N.
#include <bits/stdc++.h>
using namespace std;
 
// function to count length of binary expression of n
int countBits(int n)
{
    int count = 0;
    while (n) {
        count++;
        n >>= 1;
    }
    return count;
}
 
// Driver code
int main()
{
    int n = 32;
    cout << "Minimum value of K is = "
         << countBits(n) << endl;
    return 0;
}

// Java  program to find count of integers needed
// to express all numbers from 1 to N
 
import java.io.*;
 
class GFG {
     
// function to count length of binary expression of n
static int countBits(int n)
{
    int count = 0;
    while (n>0) {
        count++;
        n >>= 1;
    }
    return count;
}
 
// Driver code
    public static void main (String[] args) {
        int n = 32;
        System.out.println("Minimum value of K is = "+
             countBits(n));
         
    }
}

# Python3 program to find count of integers
# needed to express all numbers from 1 to N.
 
# function to count length of
# binary expression of n
def countBits(n):
 
    count = 0;
    while (n):
        count += 1;
        n >>= 1;
         
    return count;
 
# Driver code
n = 32;
print("Minimum value of K is =",
                  countBits(n));
 
# This code is contributed by mits

// C# program to find count of
// integers needed to express all
// numbers from 1 to N
using System;
 
class GFG
{
// function to count length of
// binary expression of n
static int countBits(int n)
{
    int count = 0;
    while (n > 0)
    {
        count++;
        n >>= 1;
    }
    return count;
}
 
// Driver code
static public void Main ()
{
    int n = 32;
    Console.WriteLine("Minimum value of K is = "+
                                   countBits(n));
}
}
 
// This code is contributed
// by Sach_Code

<?php
// PHP program to find count of integers
// needed to express all numbers from 1 to N.
 
// function to count length of
// binary expression of n
function countBits($n)
{
    $count = 0;
    while ($n)
    {
        $count++;
        $n >>= 1;
    }
    return $count;
}
 
// Driver code
$n = 32;
echo "Minimum value of K is = ",
      countBits($n), "\n";
 
// This code is contributed by Sachin
?>

<script>
 
// Javascript program to find count of
// integers needed to express all
// numbers from 1 to N.
 
// Function to count length of binary
// expression of n
function countBits(n)
{
    var count = 0;
    while (n)
    {
        count++;
        n >>= 1;
    }
    return count;
}
 
// Driver code
var n = 32;
document.write("Minimum value of K is = "  +
               countBits(n));
                
// This code is contributed by rrrtnx
 
</script>

producción: 

Minimum value of K is = 6

Complejidad de tiempo: O (log n)

Espacio Auxiliar: O(1)

Consulte contar bits establecidos para conocer métodos más eficientes para contar bits establecidos en un número entero.