Reduce a number to 1 by performing given operations | Set 2 | C ++ implementation of the approach ; Function to return the number of set bits in n ; Function to return the minimum steps required to reach 1 ; If n is even then divide it by 2 ; If n is 3 or the number of set bits in ( n - 1 ) is less than the number of set bits in ( n + 1 ) ; Increment the number of steps ; Return the minimum number of steps ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int set_bits ( int n ) { int count = 0 ; while ( n ) { count += n % 2 ; n /= 2 ; } return count ; } int minSteps ( int n ) { int ans = 0 ; while ( n != 1 ) { if ( n % 2 == 0 ) n /= 2 ; else if ( n == 3 or set_bits ( n - 1 ) < set_bits ( n + 1 ) ) n -- ; else n ++ ; ans ++ ; } return ans ; } int main ( ) { int n = 15 ; cout << minSteps ( n ) ; return 0 ; }