Convierta 0 a N sumando 1 o multiplicando por 2 en pasos mínimos

Dado un entero positivo N , la tarea es encontrar el número mínimo de operaciones de suma requeridas para convertir el número 0 en N , de modo que en cada operación cualquier número pueda multiplicarse por 2 o agregarle el valor 1 .

Ejemplos: 

Entrada: N = 6
Salida: 1
Explicación: Las
siguientes son las operaciones realizadas para convertir 0 a 6:
Sumar 1 –> 0 + 1 = 1.
Multiplicar 2 –> 1 * 2 = 2.
Sumar 1 –> 2 + 1 = 3 Multiplica 2 – 
> 3 * 2 = 6.
Por lo tanto número de operaciones de suma = 2.  

Entrada: N = 3
Salida: 2

Enfoque: este problema se puede resolver utilizando la técnica de manipulación de bits . En la representación de números binarios de N , mientras opera cada bit cada vez que N se vuelve impar (eso significa que se establece el bit menos significativo de N ), luego realice la operación de suma . De lo contrario, multiplique por 2 . La lógica final del problema dado es encontrar el número de bits establecidos en N .

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 number of
// set bits in N
int minimumAdditionOperation(
    unsigned long long int N)
{
 
    // Stores the count of set bits
    int count = 0;
 
    while (N) {
 
        // If N is odd, then it
        // a set bit
        if (N & 1 == 1) {
            count++;
        }
        N = N >> 1;
    }
 
    // Return the result
    return count;
}
 
// Driver Code
int main()
{
    int N = 6;
    cout << minimumAdditionOperation(N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG {
 
    // Function to count number of
    // set bits in N
    static int minimumAdditionOperation(int N)
    {
 
        // Stores the count of set bits
        int count = 0;
 
        while (N > 0) {
 
            // If N is odd, then it
            // a set bit
            if (N % 2 == 1) {
                count++;
            }
            N = N >> 1;
        }
 
        // Return the result
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 6;
        System.out.println(minimumAdditionOperation(N));
    }
}
 
// This code is contributed by dwivediyash

# python program for above approach
 
# Function to count number of
# set bits in N
def minimumAdditionOperation(N):
 
    # Stores the count of set bits
    count = 0
 
    while (N):
 
        # If N is odd, then it
        # a set bit
        if (N & 1 == 1):
            count += 1
 
        N = N >> 1
 
    # Return the result
    return count
 
# Driver Code
if __name__ == "__main__":
 
    N = 6
    print(minimumAdditionOperation(N))
 
    # This code is contributed by rakeshsahni.

// C# program for above approach
using System;
public class GFG{
     
    // Function to count number of
    // set bits in N
    static int minimumAdditionOperation(int N)
    {
     
        // Stores the count of set bits
        int count = 0;
     
        while (N != 0) {
     
            // If N is odd, then it
            // a set bit
            if ((N & 1) == 1) {
                count++;
            }
            N = N >> 1;
        }
     
        // Return the result
        return count;
    }
     
    // Driver Code
    static public void Main (){
        int N = 6;
        Console.Write(minimumAdditionOperation(N));
     
    }
}
 
// This code is contributed by AnkThon

<script>
// Javascript program for above approach
 
// Function to count number of
// set bits in N
function minimumAdditionOperation(N)
{
 
  // Stores the count of set bits
  let count = 0;
 
  while (N)
  {
   
    // If N is odd, then it
    // a set bit
    if (N & (1 == 1)) {
      count++;
    }
    N = N >> 1;
  }
 
  // Return the result
  return count;
}
 
// Driver Code
let N = 6;
document.write(minimumAdditionOperation(N));
 
// This code is contributed by saurabh_jaiswal.
</script>

2

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