Given a positive integer 
. Find the number of steps required to minimize it to 1. In a single step N either got reduced to half if it is power of 2 else N is reduced to difference of N and its nearest power of 2 which is smaller than N.
Examples:
Input : N = 2 Output : 1
Input : N = 20 Output : 3
Simple Approach: As per question a very simple and brute force approach is to iterate over N until it got reduced to 1, where reduction involve two cases:
- N is power of 2 : reduce n to n/2
- N is not power of 2: reduce n to n – (2^log2(n))
Efficient approach: Before proceeding to actual result lets have a look over bit representation of an integer n as per problem statement.
- When an integer is power of 2: In this case bit -representation includes only one set bit and that too is left most. Hence log2(n) i.e. bit-position minus One is the number of step required to reduce it to n. Which is also equal to number of set bit in n-1.
- When an integer is not power of 2:The remainder of n – 2^(log2(n)) is equal to integer which can be obtained by un-setting the left most set bit. Hence, one set bit removal count as one step in this case.
Hence the actual answer for steps required to reduce n is equal to number of set bits in n-1. Which can be easily calculated either by using the loop or any of method described in the post: Count Set bits in an Integer.
Below is the implementation of the above approach:
C++
// Cpp to find the number of step to reduce n to 1// C++ program to demonstrate __builtin_popcount()#include <iostream>using namespace std;// Function to return number of steps for reductionint stepRequired(int n){ // builtin function to count set bits return __builtin_popcount(n - 1);}// Driver programint main(){ int n = 94; cout << stepRequired(n) << endl; return 0;} |
Java
// Java program to find the number of step to reduce n to 1import java.io.*;class GFG{ // Function to return number of steps for reduction static int stepRequired(int n) { // builtin function to count set bits return Integer.bitCount(n - 1); } // Driver program public static void main(String []args) { int n = 94; System.out.println(stepRequired(n)); }}// This code is contributed by // ihritik |
Python3
# Python3 to find the number of step# to reduce n to 1 # Python3 program to demonstrate# __builtin_popcount() # Function to return number of# steps for reduction def stepRequired(n) : # step to count set bits return bin(94).count('1')# Driver Codeif __name__ == "__main__" : n = 94 print(stepRequired(n))# This code is contributed by Ryuga |
C#
// C# program to find the number of step to reduce n to 1using System;class GFG{ // function to count set bits static int countSetBits(int n) { // base case if (n == 0) return 0; else // if last bit set // add 1 else add 0 return (n & 1) + countSetBits(n >> 1); } // Function to return number of steps for reduction static int stepRequired(int n) { return countSetBits(n - 1); } // Driver program public static void Main() { int n = 94; Console.WriteLine(stepRequired(n)); }}// This code is contributed by // ihritik |
PHP
<?php// PHP program to find the number of step to reduce n to 1// recursive function to // count set bits function countSetBits($n) { // base case if ($n == 0) return 0; else return 1 + countSetBits($n & ($n - 1)); } // Function to return number of steps for reductionfunction stepRequired($n){ return countSetBits($n - 1);} // Driver program$n = 94;echo stepRequired($n); // This code is contributed by // ihritik?> |
Javascript
<script> // Javascript program to find the number of step to reduce n to 1 // function to count set bits function countSetBits(n) { // base case if (n == 0) return 0; else // if last bit set // add 1 else add 0 return (n & 1) + countSetBits(n >> 1); } // Function to return number of steps for reduction function stepRequired(n) { return countSetBits(n - 1); } let n = 94; document.write(stepRequired(n)); // This code is contributed by decode2207.</script> |
5
Time Complexity: O(1) as constant time is taken.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] There you can find 85555 more Information to that Topic: geeksforgeeks.org/count-number-of-step-required-to-reduce-n-to-1-by-following-certain-rule/ […]
… [Trackback]
[…] Read More to that Topic: geeksforgeeks.org/count-number-of-step-required-to-reduce-n-to-1-by-following-certain-rule/ […]
… [Trackback]
[…] Find More on to that Topic: geeksforgeeks.org/count-number-of-step-required-to-reduce-n-to-1-by-following-certain-rule/ […]
… [Trackback]
[…] Read More Info here to that Topic: geeksforgeeks.org/count-number-of-step-required-to-reduce-n-to-1-by-following-certain-rule/ […]