Count number of steps to cover a distance if steps can be taken in powers of 2

0 0 2 minutes read

Given a distance K to cover, the task is to find the minimum steps required to cover the distance if steps can be taken in powers of 2 like 1, 2, 4, 8, 16……..
Examples :

Input : K = 9
Output : 2

Input : K = 343 
Output : 6

The minimum steps required can be calculated by reducing K by the highest power of 2 in each step which can be obtained by counting no. of set bits in the binary representation of a number.
Below is the implementation of the above approach:

C++

// 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

// 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

Python3

# 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#

// 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

Javascript

<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>

Output:

Time Complexity : $O(log(n))$

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!