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 stepsint getMinSteps(int K){ // __builtin_popcount() is a C++ function to // count the number of set bits in a number return __builtin_popcount(k);}// Driver Codeint 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 = 343print(getMinSteps(n))# This code is contributed by# divyamohan123 |
C#
// C# program to count minimum number of stepsusing 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:
6
Time Complexity : 
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
