Given a positive integer X the task is to find an integer Y such that:
- The count of set bits is Y is equal to the count of set bits in X.
- X != Y.
- |X – Y| is minimum.
Examples:
Input: X = 92
Output: 90
90 is the closest number to 92 having
equal number of set bits.
Input: X = 17
Output: 18
Approach: A little math can lead us to the solution approach. Since the number of bits in both the numbers has to be the same, if a set bit is flipped then an unset bit will also have to be flipped.
Now the problem reduces to choosing two bits for the flipping. Suppose one bit at index i is flipped and another bit at index j (j < i) from the LSB (least significant bit). Then the absolute value of the difference between the original integer and the new one is 2i – 2j. To minimize this, i has to be as small as possible and j has to be as close to i as possible.
Since the number of set bits have to be equal, so the bit at index i must be different from the bit at index j. This means that the smallest can be the rightmost bit that’s different from the LSB, and j must be the very next bit. In summary, the correct approach is to swap the two rightmost consecutive bits that are different.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int NumUnsignBits = 64;// Function to return the number// closest to x which has equal// number of set bits as xunsigned long findNum(unsigned long x){ // Loop for each bit in x and // compare with the next bit for (int i = 0; i < NumUnsignBits - 1; i++) { if (((x >> i) & 1) != ((x >> (i + 1)) & 1)) { x ^= (1 << i) | (1 << (i + 1)); return x; } }}// Driver codeint main(){ int n = 92; cout << findNum(n); return 0;} |
Java
// Java implementation of the approachclass GFG {static int NumUnsignBits = 64;// Function to return the number// closest to x which has equal// number of set bits as xstatic long findNum(long x){ // Loop for each bit in x and // compare with the next bit for (int i = 0; i < NumUnsignBits - 1; i++) { if (((x >> i) & 1) != ((x >> (i + 1)) & 1)) { x ^= (1 << i) | (1 << (i + 1)); return x; } } return Long.MIN_VALUE;}// Driver codepublic static void main(String[] args){ int n = 92; System.out.println(findNum(n));}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach NumUnsignBits = 64; # Function to return the number # closest to x which has equal # number of set bits as x def findNum(x) : # Loop for each bit in x and # compare with the next bit for i in range(NumUnsignBits - 1) : if (((x >> i) & 1) != ((x >> (i + 1)) & 1)) : x ^= (1 << i) | (1 << (i + 1)); return x;# Driver code if __name__ == "__main__" : n = 92; print(findNum(n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System; class GFG {static int NumUnsignBits = 64;// Function to return the number// closest to x which has equal// number of set bits as xstatic long findNum(long x){ // Loop for each bit in x and // compare with the next bit for (int i = 0; i < NumUnsignBits - 1; i++) { if (((x >> i) & 1) != ((x >> (i + 1)) & 1)) { x ^= (1 << i) | (1 << (i + 1)); return x; } } return long.MinValue;}// Driver codepublic static void Main(String[] args){ int n = 92; Console.WriteLine(findNum(n));}}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the approach let NumUnsignBits = 64; // Function to return the number // closest to x which has equal // number of set bits as x function findNum(x) { // Loop for each bit in x and // compare with the next bit for (let i = 0; i < NumUnsignBits - 1; i++) { if (((x >> i) & 1) != ((x >> (i + 1)) & 1)) { x ^= (1 << i) | (1 << (i + 1)); return x; } } return Number.MIN_VALUE; } let n = 92; document.write(findNum(n));</script> |
90
Time Complexity: O(logn)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
