Cuente el número de pasos para cubrir una distancia si los pasos se pueden dar en potencias de 2

Dada una distancia K a cubrir, la tarea es encontrar los pasos mínimos requeridos para cubrir la distancia si los pasos se pueden tomar en potencias de 2 como 1, 2, 4, 8, 16…..
Ejemplos: 
 

Input : K = 9
Output : 2

Input : K = 343 
Output : 6

Los pasos mínimos requeridos se pueden calcular reduciendo K por la potencia más alta de 2 en cada paso que se puede obtener contando no. de bits establecidos en la representación binaria de un número.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to count the minimum number of steps
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the minimum number of steps
int getMinSteps(int K)
{
   // __builtin_popcount() is a C++ function to
   // count the number of set bits in a number
   return __builtin_popcount(k);
}
 
// Driver Code
int main()
{
    int n = 343;
     
    cout << getMinSteps(n)<< '\n';
 
    return 0;
}

// Java program to count minimum number of steps
import java.io.*;
 
class GFG
{
     
    // Function to count the minimum number of steps
    static int getMinSteps(int K)
    {
        // count the number of set bits in a number
        return Integer.bitCount(K);
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int n = 343;
         
        System.out.println(getMinSteps(n));
    }
}
 
// This code is contributed by AnkitRai01

# Python 3 implementation of the approach
 
# Function to count the minimum number of steps
def getMinSteps(K) :
     
    # bin(K).count("1") is a Python3 function to
    # count the number of set bits in a number
    return bin(K).count("1")
 
# Driver Code
n = 343
print(getMinSteps(n))
 
# This code is contributed by
# divyamohan123

// C# program to count minimum number of steps
using System;
     
class GFG
{
     
    // Function to count the minimum number of steps
    static int getMinSteps(int K)
    {
        // count the number of set bits in a number
        return countSetBits(K);
    }
     
    static int countSetBits(int x)
    {
        int setBits = 0;
        while (x != 0)
        {
            x = x & (x - 1);
            setBits++;
        }
        return setBits;
    }
     
    // Driver Code
    public static void Main (String[] args)
    {
        int n = 343;
         
        Console.WriteLine(getMinSteps(n));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
    // Javascript program to count minimum number of steps
     
    // Function to count the minimum number of steps
    function getMinSteps(K)
    {
        // count the number of set bits in a number
        return countSetBits(K);
    }
       
    function countSetBits(x)
    {
        let setBits = 0;
        while (x != 0)
        {
            x = x & (x - 1);
            setBits++;
        }
        return setBits;
    }
     
    let n = 343;
           
      document.write(getMinSteps(n));
     
    // This code is contributed by decode2207.
</script>

6

Complejidad del tiempo: 

Espacio Auxiliar: O(1)