Next greater integer having one more number of set bits
Given a positive integer ‘n’ having ‘x’ number of set bits in its binary representation. The problem is to find the next greater integer(smallest integer greater than n), having (x+1) number of set bits in its binary representation.
Examples :
Input : 10 Output : 11 (10)10 = (1010)2 is having 2 set bits. (11)10 = (1011)2 is having 3 set bits and is the next greater. Input : 39 Output : 47
Approach: Following are the steps:
- Find the position of the rightmost unset bit(considering last bit at position 0, second last bit at position 1 and so on) in the binary representation of n.
- Let the position be represented by pos.
- Set the bit at position pos. Refer this post.
- If there are no unset bits in the binary representation, then perform bitwise left shift by 1 on the given number and then add 1 to it.
How to get the position of rightmost unset bit?
- Perform bitwise not on the given number(operation equivalent to 1’s complement).Let it be num = ~n.
- Get the position of rightmost set bit of num.
C++
// C++ implementation to find the next greater integer // with one more number of set bits #include <bits/stdc++.h> using namespace std; // function to find the position of rightmost // set bit. Returns -1 if there are no set bits int getFirstSetBitPos( int n) { return (log2(n&-n)+1) - 1; } // function to find the next greater integer int nextGreaterWithOneMoreSetBit( int n) { // position of rightmost unset bit of n // by passing ~n as argument int pos = getFirstSetBitPos(~n); // if n consists of unset bits, then // set the rightmost unset bit if (pos > -1) return (1 << pos) | n; //n does not consists of unset bits return ((n << 1) + 1); } // Driver program to test above int main() { int n = 10; cout << "Next greater integer = " << nextGreaterWithOneMoreSetBit(n); return 0; } |
Java
// Java implementation to find the next greater integer // with one more number of set bits class GFG { // function to find the position of rightmost // set bit. Returns -1 if there are no set bits static int getFirstSetBitPos( int n) { return (( int )(Math.log(n & -n) / Math.log( 2 )) + 1 ) - 1 ; } // function to find the next greater integer static int nextGreaterWithOneMoreSetBit( int n) { // position of rightmost unset bit of n // by passing ~n as argument int pos = getFirstSetBitPos(~n); // if n consists of unset bits, then // set the rightmost unset bit if (pos > - 1 ) return ( 1 << pos) | n; // n does not consists of unset bits return ((n << 1 ) + 1 ); } // Driver code public static void main(String[] args) { int n = 10 ; System.out.print( "Next greater integer = " + nextGreaterWithOneMoreSetBit(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 implementation to find # the next greater integer with # one more number of set bits import math # Function to find the position # of rightmost set bit. Returns -1 # if there are no set bits def getFirstSetBitPos(n): return (( int )(math.log(n & - n) / math.log( 2 )) + 1 ) - 1 # Function to find the next greater integer def nextGreaterWithOneMoreSetBit(n): # position of rightmost unset bit of # n by passing ~n as argument pos = getFirstSetBitPos(~n) # if n consists of unset bits, then # set the rightmost unset bit if (pos > - 1 ): return ( 1 << pos) | n # n does not consists of unset bits return ((n << 1 ) + 1 ) # Driver code n = 10 print ( "Next greater integer = " , nextGreaterWithOneMoreSetBit(n)) # This code is contributed by Anant Agarwal. |
C#
// C# implementation to find the next greater // integer with one more number of set bits using System; class GFG { // function to find the position of rightmost // set bit. Returns -1 if there are no set bits static int getFirstSetBitPos( int n) { return (( int )(Math.Log(n & -n) / Math.Log(2)) + 1) - 1; } // function to find the next greater integer static int nextGreaterWithOneMoreSetBit( int n) { // position of rightmost unset bit of n // by passing ~n as argument int pos = getFirstSetBitPos(~n); // if n consists of unset bits, then // set the rightmost unset bit if (pos > -1) return (1 << pos) | n; // n does not consists of unset bits return ((n << 1) + 1); } // Driver code public static void Main() { int n = 10; Console.Write( "Next greater integer = " + nextGreaterWithOneMoreSetBit(n)); } } // This code is contributed by Anant Agarwal. |
PHP
<?php // PHP implementation to find the // next greater integer with // one more number of set bits // function to find the position // of rightmost set bit. Returns // -1 if there are no set bits function getFirstSetBitPos( $n ) { return (log( $n & - $n + 1)) - 1; } // function to find the // next greater integer function nextGreaterWithOneMoreSetBit( $n ) { // position of rightmost unset bit of n // by passing ~n as argument $pos = getFirstSetBitPos(~ $n ); // if n consists of unset bits, then // set the rightmost unset bit if ( $pos > -1) return (1 << $pos ) | $n ; //n does not consists of unset bits return (( $n << 1) + 1); } // Driver Code $n = 10; echo "Next greater integer = " , nextGreaterWithOneMoreSetBit( $n ); // This code is contributed by Ajit ?> |
Javascript
<script> // Javascript implementation to find the next greater integer // with one more number of set bits // function to find the position of rightmost // set bit. Returns -1 if there are no set bits function getFirstSetBitPos(n) { return (parseInt(Math.log(n&-n)/Math.log(2))+1) - 1; } // function to find the next greater integer function nextGreaterWithOneMoreSetBit(n) { // position of rightmost unset bit of n // by passing ~n as argument var pos = getFirstSetBitPos(~n); // if n consists of unset bits, then // set the rightmost unset bit if (pos > -1) return (1 << pos) | n; //n does not consists of unset bits return ((n << 1) + 1); } // Driver program to test above var n = 10; document.write( "Next greater integer = " + nextGreaterWithOneMoreSetBit(n)); </script> |
Output :
Next greater integer = 11
Time Complexity: O(log(log N))
Auxiliary Space: O(1)