Número mínimo de monedas de valor igual a potencias de 2 requeridas para obtener N

Dado un número entero N , la tarea es encontrar el número mínimo de monedas de la forma 2 ⁱ requeridas para hacer un cambio de N centavos.

Ejemplos:

Entrada: N = 5 
Salida: 2 
Explicación: 
Los valores posibles de las monedas son: {1, 2, 4, 8, …} 
Las formas posibles de dar cambio por N centavos son las siguientes: 
5 = 1 + 1 + 1 + 1 + 1 
5 = 1 + 2 + 2 
5 = 1 + 4 (Mínimo) 
Por lo tanto, la salida requerida es 2

Entrada: N = 4 
Salida: 4

Enfoque ingenuo: el enfoque más simple para resolver este problema es almacenar todos los valores posibles de las monedas en una array e imprimir el recuento mínimo de monedas necesario para realizar un cambio de N centavos mediante la programación dinámica . 
Tiempo Complejidad: O(N ² )  
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el hecho de que cualquier número se puede representar en forma de una potencia de 2 s. La idea es contar los bits establecidos de N e imprimir el conteo obtenido. Siga los pasos a continuación para resolver el problema:

• Iterar sobre los bits en la representación binaria de N y verificar si el bit actual está configurado o no. Si se encuentra que es cierto, entonces incremente el conteo.
• Finalmente, imprima el conteo total obtenido.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count of set bit in N
void count_setbit(int N)
{
 
    // Stores count of set bit in N
    int result = 0;
 
    // Iterate over the range [0, 31]
    for (int i = 0; i < 32; i++) {
 
        // If current bit is set
        if ((1 << i) & N) {
 
            // Update result
            result++;
        }
    }
    cout << result << endl;
}
 
// Driver Code
int main()
{
    int N = 43;
 
    count_setbit(N);
    return 0;
}

// C program for above approach
#include <stdio.h>
 
// Function to count of set bit in N
void count_setbit(int N)
{
 
    // Stores count of set bit in N
    int result = 0;
 
    // Iterate over the range [0, 31]
    for (int i = 0; i < 32; i++) {
 
        // If current bit is set
        if ((1 << i) & N) {
 
            // Update result
            result++;
        }
    }
    printf("%d\n", result);
}
 
// Driver Code
int main()
{
    int N = 43;
 
    count_setbit(N);
    return 0;
}

// Java program for above approach
public class Main {
 
    // Function to count of set bit in N
    public static void count_setbit(int N)
    {
        // Stores count of set bit in N
        int result = 0;
 
        // Iterate over the range [0, 31]
        for (int i = 0; i < 32; i++) {
 
            // If current bit is set
            if (((1 << i) & N) > 0) {
 
                // Update result
                result++;
            }
        }
 
        System.out.println(result);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        int N = 43;
        count_setbit(N);
    }
}

# Python program for above approach
 
# Function to count of set bit in N
def count_setbit(N):
 
    # Stores count of set bit in N
    result = 0
     
    # Iterate over the range [0, 31]
    for i in range(32):
     
       # If current bit is set  
       if( (1 << i) & N ):
            
           # Update result
           result = result + 1
     
    print(result)
 
if __name__ == '__main__':
 
    N = 43
    count_setbit(N)

// C# program for above approach
using System;
class GFG {
 
    // Function to count of setbit in N
    static void count_setbit(int N)
    {
 
        // Stores count of setbit in N
        int result = 0;
 
        // Iterate over the range [0, 31]
        for (int i = 0; i < 32; i++) {
 
            // If current bit is set
            if (((1 << i) & N) > 0) {
 
                // Update result
                result++;
            }
        }
 
        Console.WriteLine(result);
    }
 
    // Driver Code
    static void Main()
    {
 
        int N = 43;
        count_setbit(N);
    }
}

<script>
// Javascript program to implement
// the above approach
 
    // Function to count of set bit in N
    function count_setbit(N)
    {
        // Stores count of set bit in N
        let result = 0;
   
        // Iterate over the range [0, 31]
        for (let i = 0; i < 32; i++) {
   
            // If current bit is set
            if (((1 << i) & N) > 0) {
   
                // Update result
                result++;
            }
        }
        document.write(result);
    }
 
// Driver Code
        let N = 43;
        count_setbit(N); 
     
    // This code is contributed by souravghosh0416.
</script>

4

Complejidad de Tiempo: O(log ₂ (N))
Espacio Auxiliar: O(1)