problemmediumalgorithms

Find the nearest numbers that have same number of 1s for an integer

MediumUpdated: Aug 2, 2025

Problem

Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation.

Examples

Example 1:

Input: number = 3
Output: 5
Explanation: Next higher number for 3 is 5. i.e. (00000011 => 00000101). Likewise next lower number of 5 is 3.

Solution

Method 1 - Adding or subtracting 1 until we have same number of 1s

For the next largest, keep adding 1 to the number until find the number that has same number of 1 bits. For the next smallest, keep decreasing 1.

Code

Java
public static int findNextSmallest(int number) {
	int result = number - 1;

	while (Integer.bitCount(result) != Integer.bitCount(number)) {
		result--;
	}

	return result;
}


public static int findNextLargest(int number) {
	int result = number + 1;

	while (Integer.bitCount(result) != Integer.bitCount(number)) {
		result++;
	}

	return result;
}

Definitely gonna work but terribly boring. We know this is not what the interviewer expects, he wants some bit manipulation.

Method 2- Change the bits

For getting the next higher number

  • Traverse from right to left i.e. LSB to MSB. Once we’ve passed a 1, turn on the next 0. We’ve now increased the number by 2^i. Yikes! Example: xxxxx011100 becomes xxxxx111100.

  • Turn off the one that’s just to the right side of that. We’re now bigger by 2^i - 2^(i-1). Example: xxxxx111100 becomes xxxxx101100

  • Make the number as small as possible by rearranging all the 1s to be as far right as possible: Example: xxxxx101100 becomes xxxxx100011

For the next smaller number We can do something like this.

int getNextSmaller(int num) {
	return ~getNextLarger(~num);
}

i.e. follow the above algorithm for number's complement.

Code

Java
public boolean GetBit(int n, int index) {
	return ((n & (1<< index)) > 0);
}


public int SetBit(int n, int index, boolean b) {
	if (b) {
		return n | (1<< index);
	} else {
		int mask = ~(1<< index);
		return n & mask;
	}
}


public int GetNext_NP(int n) {
	if (n <= 0)
		return -1;
	int index = 0;
	int countOnes = 0;

	// Find first one.
	while (!GetBit(n, index))
		index++;

	// Turn on next zero.
	while (GetBit(n, index)) {
		index++;
		countOnes++;
	}

	n = SetBit(n, index, true);

	// Turn off previous one
	index--;
	n = SetBit(n, index, false);
	countOnes--;

	// Set zeros
	for (int i = index - 1; i >= countOnes; i--) {
		n = SetBit(n, i, false);
	}

	// Set ones
	for (int i = countOnes - 1; i >= 0; i--) {
		n = SetBit(n, i, true);
	}

	return n;
}


public int GetPrevious_NP(int n) {
	if (n <= 0)
		return -1; // Error
	int index = 0;
	int countZeros = 0;

	// Find first zero.
	while (GetBit(n, index))
		index++;

	// Turn off next 1.
	while (!GetBit(n, index)) {
		index++;
		countZeros++;
	}

	n = SetBit(n, index, false);

	// Turn on previous zero
	index--;
	n = SetBit(n, index, true);
	countZeros--;

	// Set ones
	for (int i = index - 1; i >= countZeros; i--) {
		n = SetBit(n, i, true);
	}

	// Set zeros
	for (int i = countZeros - 1; i >= 0; i--) {
		n = SetBit(n, i, false);
	}

	return n;
}

References

Comments