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 bitsint getFirstSetBitPos(int n){ return (log2(n&-n)+1) - 1;}// function to find the next greater integerint 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 aboveint 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 bitsclass 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 bitsimport math# Function to find the position# of rightmost set bit. Returns -1# if there are no set bitsdef getFirstSetBitPos(n): return ((int)(math.log(n & -n) / math.log(2)) + 1) - 1# Function to find the next greater integerdef 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 coden = 10print("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 bitsusing 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 bitsfunction getFirstSetBitPos($n){ return (log($n & -$n + 1)) - 1;}// function to find the// next greater integerfunction 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)
If you like neveropen and would like to contribute, you can also write an article using write.neveropen.co.uk or mail your article to review-team@neveropen.co.uk. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!