Find closest integer with the same weight

0 0 4 minutes read

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 2ⁱ – 2^j. 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 x
unsigned 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 code
int main()
{
    int n = 92;
 
    cout << findNum(n);
 
    return 0;
}

Java

// Java implementation of the approach
class GFG 
{
static int NumUnsignBits = 64;
 
// Function to return the number
// closest to x which has equal
// number of set bits as x
static 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 code
public 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 approach
using System;
     
class GFG 
{
static int NumUnsignBits = 64;
 
// Function to return the number
// closest to x which has equal
// number of set bits as x
static 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 code
public 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>

Output:

Time Complexity: O(logn)

Auxiliary Space: O(1)

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 zambiatek!