Nearest numbers with the same number of set bits
Given a positive integer ‘n’, your task is to find the next smallest integer and the previous largest integer having the exact number of ‘1’ bits set in their binary representation as ‘n’.

Example:

‘n = 6’ The binary representation of 6 = ‘0110’, which has two ‘1’ bits set. Next smallest integer = 9 = ‘1001’, the smallest integer greater than 6 having two ‘1’ bits set. Previous largest integer = 5 = ‘0101’, largest integer smaller than 6 having two ‘1’ bits set. Therefore, the answer is {9, 5}.

Note:

1. ‘n’ is a positive integer greater than one. 2. For any given integer ‘n’, there is always a positive integer smaller than ‘n’ having the exact number of ‘1’ bits set. 3. Don’t print anything. Just implement the function and return the answer. 4. ‘n’ can have a max of ‘30’ bits.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. The next line of each test case consists of a single line containing the integer ‘n’.

Output format:

For each test case, print the next smallest integer, the previous largest integer to ‘n’ with the exact number of ‘1’ bits set. The output of each test case should be printed in a new line.

Constraints:

1

Question

Nearest numbers with the same number of set bits

Given a positive integer ‘n’, your task is to find the next smallest integer and the previous largest integer having the exact number of ‘1’ bits set in their binary representation as ‘n’.

Example:

‘n = 6’
The binary representation of 6 = ‘0110’, which has two ‘1’ bits set.
Next smallest integer = 9 = ‘1001’, the smallest integer greater than 6 having two ‘1’ bits set.
Previous largest integer = 5 = ‘0101’, largest integer smaller than 6 having two ‘1’ bits set.
Therefore, the answer is {9, 5}.

Note:

1. ‘n’ is a positive integer greater than one.
2. For any given integer ‘n’, there is always a positive integer smaller than ‘n’ having the exact number of ‘1’ bits set.
3. Don’t print anything. Just implement the function and return the answer.
4. ‘n’ can have a max of ‘30’ bits.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next line of each test case consists of a single line containing the integer ‘n’.

Output format:

For each test case, print the next smallest integer, the previous largest integer to ‘n’ with the exact number of ‘1’ bits set.

The output of each test case should be printed in a new line.

Constraints:

1 <= T <= 10000
‘n’ can have ‘30’ bits at max

Where ‘T’ is the number of test cases, and ‘n’ is the given integer.

Time limit: 1 second

Accepted Answer

Approach :

When we observe the binary sequence from 0 to 2n – 1 (n is no. of bits), right most bits (least significant) vary rapidly than left most bits. The idea is to find right most string of 1’s in x, and shift the pattern to right extreme, except the left most bit in the pattern. Shift the left most bit in the pattern (omitted bit) to left part of x by one position.

//Pseudo Code :

int findNextGreaterNum(int n)
{
int ct=0 , subt=0, idx=0;
for(int i=0; i<32; i++)
{
while(n&(1<0)
{
idx=i; //idx-1 will hold the position of the leftmost one in the rightmost 1's pattern
break;
}
}
int add=(1< int ans=n-subt+add;
cout< return ans;
}

Accepted Answer

Brute force

The brute force approach would be to count the number of ‘1’ bits in ‘n’ and then increment (or decrement) from ‘n’ until we find an integer with an exact count of ‘1’ bits.

Count the number of ‘1’ bits set in ‘n’.
Increment ‘n’ until we find an integer with an exact count of ‘1’ bits.
Decrement ‘n’ until we find an integer with an exact count of ‘1’ bits.

Space Complexity: O(1)Explanation:

O(1),

Since we are not using any extra space, space complexity is constant.

Time Complexity: O(n)Explanation:

O(n), where ‘n’ is the given integer.

We know that ‘2*n’ and ‘n’ have the same count of ‘1’ bits. So in the worst case, we have to iterate from ‘n’ to ‘2*n’ (i.e., O(‘n’)) for the next smallest integer and from ‘n’ to ‘n/2’ (i.e., O(‘n’)) for the previous largest integer. Hence, the total time complexity is ‘O(n)’.

Java (SE 1.8)

/*
    Time Complexity : O(N)
    Space Complexity : O(1)

    where N is the given integer.
*/

import java.util.ArrayList;

public class Solution {
	// Function to count the number of ones in the binary representation of 'n'
	private static int countOnes(int n) {
		int count = 0;

		for (; n != 0; n >>= 1) {
			if ((n & 1) != 0) {
				count++;
			}
		}

		return count;
	}

	public static ArrayList nearestNumbers(int n) {

		ArrayList res = new ArrayList();

		int count = countOnes(n);

		int next = n + 1, prev = n - 1;

		while (countOnes(next) != count) {
			// Increment 'next' until 'next' and 'n' have the same number of ones
			next++;
		}

		while (countOnes(prev) != count) {
			// Decrement 'prev' until 'prev' and 'n' have the same number of ones
			prev--;
		}

		res.add(next);
		res.add(prev);

		return res;
	}
}

Python (3.5)

'''



    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the given integer.



'''



def countOnes(n):



    count = 0

    while(n != 0):



        if(n & 1):

            count += 1



        n = n >> 1



    return count





def nearestNumbers(n):



    res = [0, 0]



    # Function to count the number of ones in the binary representation of 'n'

    count = countOnes(n)

    next = n + 1

    prev = n - 1



    while (countOnes(next) != count):



        # Increment 'next' until 'next' and 'n' have the same number of ones

        next += 1



    while (countOnes(prev) != count):



        # Decrement 'prev' until 'prev' and 'n' have the same number of ones

        prev -= 1



    res[0] = next

    res[1] = prev

    return res

C++ (g++ 5.4)

/*

    Time Complexity : O(N)

    Space Complexity : O(1)



    where N is the given integer.

*/



// Function to count the number of ones in the binary representation of 'n'

int countOnes(int n) {

    int count = 0;



    for (; n != 0; n >>= 1) {

        if (n & 1) {

            count++;

        }

    }



    return count;

}



vector nearestNumbers(int n) {

    vector res(2);

    int count = countOnes(n);

    int next = n + 1, prev = n - 1;



    while (countOnes(next) != count) {  // Increment 'next' until 'next' and 'n' have the same number of ones

        next++;

    }



    while (countOnes(prev) != count) {  // Decrement 'prev' until 'prev' and 'n' have the same number of ones

        prev--;

    }



    res[0] = next;

    res[1] = prev;



    return res;

}

Accepted Answer

Bit-manipulation

Observation: Consider the location of two bits for a number ‘n’ as ‘i’ and ‘j’. To maintain the same number of 1 bit in ‘n’, if we flip the ‘i-th’ bit from 1 to 0, we must convert the ‘j-th’ bit from 0 to 1. If ‘i’ is to the left of ‘j’ then the number will increase. Otherwise, it will decrease.

1. To find the next smallest number:

Let 'next' be the next smallest number to ‘n’ having the same count of ‘1’ bits as ‘n’. To obtain 'next' from ‘n’ we observe:

In ‘n’, if we flip a bit from 0 to 1 then we must flip a bit from 1 to 0.
'next' can be greater than ‘n’ only if the flipped 0 bit was left to the 1 bit.
'next' has to be greater than ‘n’ but not too big, so we need to flip the rightmost 0 bit, which has a 1 bit on its right, i.e., the rightmost non-trailing zero.

Steps to obtain 'next':

Initialize 'next = n’ and perform the following bit operations on 'next'.
Let ‘r’ be the position of the rightmost non-trailing zero in 'next'. Flip the bit at position ‘r’ from 0 to 1.
Let ‘c’ be the number of 1’s to the right of ‘r’, which means ‘r > c’. Set all the bits to the right of ‘r’ to 0.
After this, 'next' becomes greater than ‘n’ and has ‘c-1’ less 1’s than ‘n’. So, we need to flip ‘c-1’ bits of 'next' from 0 to 1 to make the 'next' the smallest number greater than ‘n’ having the same count of ‘1’ bits as n.
All the ‘r-1’ bits to the right of ‘r’ are 0 and ‘r > c’. Flip the rightmost ‘c-1’ bits from 0 to 1 to get the smallest valid value of 'next'. Return 'next' as the answer.

2. To find the previous largest number:

Let 'prev' be the previous largest number to ‘n’ having the same count of ‘1’ bits as ‘n’. we follow a similar approach as above. Instead of flipping the rightmost non-trailing zero, the only difference is that we flip the rightmost non-trailing one because here, we want 'prev' to be smaller than ‘n’.

Steps to obtain 'prev':

Initialize 'prev = n’ and perform the following bit operations on 'prev'.
Let ‘r’ be the rightmost non-trailing one in 'prev' and ‘c’ be the number of 1’s to the right of ‘r’, which means ‘c+1 < r’.
Set the bit at ‘r’ and all the bits to the right of ‘r’ to 0.
After this, 'prev' becomes smaller than ‘n’ and has ‘c+1’ less 1s than ‘n’. So, we need to flip ‘c+1’ bits from the right of ‘r’ from 0 to 1 to make 'prev' the largest number smaller than ‘n’ having the same count of ‘1’ bits as ‘n’.
All the ‘r-1’ bits to the right of ‘r’ are 0 and ‘r > c+1’. Flip ‘c+1’ bits immediately to the right of ‘r’ from 0 to 1 to get the largest valid value of 'prev'. Return 'prev' as the answer.

Space Complexity: O(1)Explanation:

O(1)

Since we are not using any extra space, space complexity is constant.

Time Complexity: O(logn)Explanation:

O(log(n)), where ‘n’ is the given integer.

The integer ‘n’ has ‘log(n)’ bits. In the worst case, to obtain ‘next’ we need to flip ‘2*log(n) - 2’, and to get ‘prev’ we need to flip ‘2*log(n) - 2’ bits. Hence, the total time complexity is ‘O(log(n))’.

Java (SE 1.8)

/*
    Time Complexity : O(log(N))
    Space Complexity : O(1)

    where N is the given integer.
*/

import java.util.ArrayList;

public class Solution {
	// Function to find the next smallest number
	private static int getNext(int n) {
		int next = n;
		int c0 = 0, c1 = 0;

		for (int i = n; i > 0 && ((i & 1) == 0); i >>= 1) {
			// Trailing zeros in 'n'
			c0++;
		}

		for (int i = (n >> c0); i > 0 && ((i & 1) != 0); i >>= 1) {
			// Trailing ones after the trailing zeros in 'n'
			c1++;
		}

		// Postion of the rightmost non-trailing zero bit
		int r = c0 + c1;

		// Set the 'r-th' bit to one
		next |= (1 << r);

		// Set all bits to the right of 'r' to zero
		next &= (~0) << r;

		// Set the rightmost 'c1 - 1' bits to one
		next |= (1 << (c1 - 1)) - 1;

		return next;
	}

	// Function to find the previous largest number
	private static int getPrev(int n) {
		int prev = n;
		int c1 = 0, c0 = 0;

		for (int i = n; i > 0 && ((i & 1) != 0); i >>= 1) {
			// Trailing ones in 'n'
			c1++;
		}

		for (int i = (n >> c1); i > 0 && ((i & 1) == 0); i >>= 1) {
			// Trailing zeros after the trailing ones in 'n'
			c0++;
		}
		// Postion of the rightmost non-trailing one bit
		int r = c0 + c1;

		// Set the bit at 'r' and all the bits to the right of 'r' to zero
		prev &= (~0) << (r + 1);

		// Sequence of 'c1 + 1' trailing ones
		int bitmask = (1 << (c1 + 1)) - 1;

		// Set 'c1 + 1' bits immediately to the right of 'r' to one
		prev |= bitmask << (c0 - 1);

		return prev;
	}

	public static ArrayList nearestNumbers(int n) {

		ArrayList res = new ArrayList();

		res.add(getNext(n));
		res.add(getPrev(n));

		return res;
	}
}

C++ (g++ 5.4)

/*

    Time Complexity : O(log(N))

    Space Complexity : O(1)



    where N is the given integer.

*/



// Function to find the next smallest number

int getNext(int n) {

    int next = n;

    int c0 = 0, c1 = 0;



    for (int i = n; i > 0 && !(i & 1); i >>= 1) {  // Trailing zeros in 'n'

        c0++;

    }



    for (int i = (n >> c0); i > 0 && (i & 1); i >>= 1) {  // Trailing ones after the trailing zeros in 'n'

        c1++;

    }



    int r = c0 + c1;  // Postion of the rightmost non-trailing zero bit



    next |= (1 << r);  // Set the 'r-th' bit to one



    next &= (~0) << r;  // Set all bits to the right of 'r' to zero



    next |= (1 << (c1 - 1)) - 1;  // Set the rightmost 'c1 - 1' bits to one



    return next;

}



// Function to find the previous largest number

int getPrev(int n) {

    int prev = n;

    int c1 = 0, c0 = 0;



    for (int i = n; i > 0 && (i & 1); i >>= 1) {  // Trailing ones in 'n'

        c1++;

    }



    for (int i = (n >> c1); i > 0 && !(i & 1); i >>= 1) {  // Trailing zeros after the trailing ones in 'n'

        c0++;

    }



    int r = c0 + c1;  // Postion of the rightmost non-trailing one bit



    prev &= (~0) << (r + 1);  // Set the bit at 'r' and all the bits to the right of 'r' to zero



    int bitmask = (1 << (c1 + 1)) - 1;  // Sequence of 'c1 + 1' trailing ones

    prev |= bitmask << (c0 - 1);        // Set 'c1 + 1' bits immediately to the right of 'r' to one



    return prev;

}



vector nearestNumbers(int n) {

    vector res(2);



    res[0] = getNext(n);

    res[1] = getPrev(n);



    return res;

}

Python (3.5)

'''



    Time Complexity : O(log(N))

    Space Complexity : O(1)



    where N is the given integer.



'''



def getNext(n):



    next = n

    c0 = 0

    c1 = 0



    i = n

    while(i > 0 and not i & 1):



        # Trailing zeros in 'n'

        c0 += 1



        i = i >> 1



    i = (n >> c0)

    while(i > 0 and i & 1):



        # Trailing ones after the trailing zeros in 'n'

        c1 += 1



        i = i >> 1



    r = c0 + c1     # Postion of the rightmost non-trailing zero bit



    next |= (1 << r)    # Set the 'r-th' bit to one



    next &= (~0) << r   # Set all bits to the right of 'r' to zero



    next |= (1 << (c1 - 1)) - 1     # Set the rightmost 'c1 - 1' bits to one



    return next





def getPrev(n):

    prev = n

    c1 = 0

    c0 = 0



    i = n

    while(i > 0 and i & 1):



        # Trailing ones in 'n'

        c1 += 1



        i = i >> 1



    i = n >> c1

    while(i > 0 and not i & 1):



        # Trailing zeros after the trailing ones in 'n'

        c0 += 1



        i = i >> 1



    r = c0 + c1   # Postion of the rightmost non-trailing one bit



    # Set the bit at 'r' and all the bits to the right of 'r' to zero

    prev &= (~0) << (r + 1)



    bitmask = (1 << (c1 + 1)) - 1  # Sequence of 'c1 + 1' trailing ones

    # Set 'c1 + 1' bits immediately to the right of 'r' to one

    prev |= bitmask << (c0 - 1)



    return prev





def nearestNumbers(n):



    res = [0, 0]



    # Function to find the next smallest number

    res[0] = getNext(n)



    # Function to find the previous largest number

    res[1] = getPrev(n)



    return res

Accepted Answer

Arithmetic approach

This approach is similar to the bit-manipulation approach, but we want to use as little bit-manipulation as possible.

1. To find the next smallest number:

Let 'next' be the next smallest number to ‘n’ having the same count of ‘1’ bits as ‘n’.

If ‘r’ is the position of the rightmost non-trailing zero in ‘n’, ‘c1’ is the number of 1’s to the right of ‘r’, and ‘c0’ is the number of trailing 0’s in ‘n’, we have ‘r = c0 + c1’.

After initializing ‘next = n’, in our previous approach we performed the following operations on ‘next’:

Set the ‘r-th’ bit to one.
Set all the bits to the right of ‘r’ to zero.
Set the rightmost ‘c1-1’ bits to one.
Observe that we can quickly do the first two steps by flipping all the trailing 0’s to 1 (making all the bits to the right of ‘r’ one) and then adding one. Here adding one flips all the 1’s to the right of ‘r’ to zero and sets the ‘r-th’ bit to one. We can write this arithmetically as follows:
- ‘next += 2^(c0) - 1’ (Set trailing 0’s to 1, making all the bits to the right of ‘r’ one)
- ‘next += 1’ (Flip all 1’s to the right of ‘r’ to 0 and set ‘r-th’ bit to one)
- Similarly, we can perform the third step, ‘next += 2^(c1-1) - 1’ (Flip the rightmost ‘c1-1’ bits from 0 to 1)
- After writing the above steps in a single equation, we get:
  - ‘next = n + (2^(c0) - 1) + 1 + (2^(c1-1) - 1)’ (Initially, ‘next = n’) Therefore, ‘next = n + 2^(c0) + 2^(c1-1) - 1’

2. To find the previous largest number:

Let ‘prev’ be the previous largest number to ‘n’ having the same count of ‘1’ bits as ‘n’.

If ‘r’ is the position of the rightmost non-trailing one in ‘n’, ‘c0’ is the number of 0’s to the right of ‘r’, and ‘c1’ is the number of trailing 1’s in ‘n’, we have ‘r = c0 + c1’.

After initializing ‘prev = n’, in our previous approach, we performed the following operations on ‘prev’:

Set the ‘r-th’ bit to zero.
Set all the bits to the right of ‘r’ to one.
Set the rightmost ‘c0-1’ bits to zero.
We can do the first two steps arithmetically as follows:
- ‘prev -= 2^(c1) - 1’ (Remove the trailing 1’s, making all the bits to the right of ‘r’ zero)
- ‘prev -= 1’ (Flip all 0’s to the right of ‘r’ to 1 and the ‘r-th’ bit from one to zero)
- Similarly, we can perform the third step, ‘prev -= 2^(c0-1) - 1’ (Flip the rightmost ‘c0-1’ bits from 1 to 0)
- After writing the above steps in a single equation, we get:
  - ‘prev = n - (2^(c1) - 1) - 1 - (2^(c0-1) - 1)’ (Initially, ‘prev = n’)
  - Therefore, ‘prev = n - 2^(c1) - 2^(c0-1) + 1’

Note: We can calculate ‘2^x’ efficiently using the left-shift (‘<<’) operator.

‘2^x = 1<= 0’ and ‘2^x’ is in the valid integer range)

Space Complexity: O(1)Explanation:

O(1)

Since we are not using any extra space, space complexity is constant.

Time Complexity: O(logn)Explanation:

O(log(n)), where ‘n’ is the given integer.

The integer ‘n’ has ‘log(n)’ bits. In the worst case, to obtain ‘p’, ‘c1’, and ‘c0’, we need to traverse all the ‘log(n)’ bits. The left-shift operation used to calculate powers of ‘2’ requires constant time. Hence, the total time complexity is ‘O(log(n))’.

Java (SE 1.8)

/*
    Time Complexity : O(log(N))
    Space Complexity : O(1)

    where N is the given integer.
*/

import java.util.ArrayList;

public class Solution {
	// Function to find the next smallest number
	private static int getNext(int n) {
		int c0 = 0, c1 = 0;

		for (int i = n; i > 0 && ((i & 1) == 0); i >>= 1) {
			// Trailing zeros in 'n'
			c0++;
		}

		for (int i = (n >> c0); i > 0 && ((i & 1) != 0); i >>= 1) {
			// Trailing ones after the trailing zeros in 'n'
			c1++;
		}

		int next = n + (1 << c0) + (1 << (c1 - 1)) - 1;

		return next;
	}

	// Function to find the previous largest number
	private static int getPrev(int n) {
		int c1 = 0, c0 = 0;

		for (int i = n; i > 0 && ((i & 1) != 0); i >>= 1) {
			// Trailing ones in 'n'
			c1++;
		}

		for (int i = (n >> c1); i > 0 && ((i & 1) == 0); i >>= 1) {
			// Trailing zeros after the trailing ones in 'n'
			c0++;
		}

		int prev = n - (1 << c1) - (1 << (c0 - 1)) + 1;

		return prev;
	}

	public static ArrayList nearestNumbers(int n) {

		ArrayList res = new ArrayList();

		res.add(getNext(n));
		res.add(getPrev(n));

		return res;
	}
}

C++ (g++ 5.4)

/*

    Time Complexity : O(log(N))

    Space Complexity : O(1)



    where N is the given integer.

*/



// Function to find the next smallest number

int getNext(int n) {

    int c0 = 0, c1 = 0;



    for (int i = n; i > 0 && !(i & 1); i >>= 1) {  // Trailing zeros in 'n'

        c0++;

    }



    for (int i = (n >> c0); i > 0 && (i & 1); i >>= 1) {  // Trailing ones after the trailing zeros in 'n'

        c1++;

    }



    int next = n + (1 << c0) + (1 << (c1 - 1)) - 1;



    return next;

}



// Function to find the previous largest number

int getPrev(int n) {

    int c1 = 0, c0 = 0;



    for (int i = n; i > 0 && (i & 1); i >>= 1) {  // Trailing ones in 'n'

        c1++;

    }



    for (int i = (n >> c1); i > 0 && !(i & 1); i >>= 1) {  // Trailing zeros after the trailing ones in 'n'

        c0++;

    }



    int prev = n - (1 << c1) - (1 << (c0 - 1)) + 1;



    return prev;

}



vector nearestNumbers(int n) {

    vector res(2);



    res[0] = getNext(n);

    res[1] = getPrev(n);



    return res;

}

Python (3.5)

'''



    Time Complexity : O(log(N))

    Space Complexity : O(1)



    where N is the given integer.



'''



def getNext(n):



    c0 = 0

    c1 = 0



    i = n

    while(i > 0 and not i & 1):



        # Trailing zeros in 'n'

        c0 += 1



        i = i >> 1



    i = (n >> c0)

    while(i > 0 and i & 1):



        # Trailing ones after the trailing zeros in 'n'

        c1 += 1



        i = i >> 1



    next = n + (1 << c0) + (1 << (c1 - 1)) - 1



    return next





def getPrev(n):

    c1 = 0

    c0 = 0



    i = n

    while(i > 0 and i & 1):



        # Trailing ones in 'n'

        c1 += 1



        i = i >> 1



    i = (n >> c1)

    while(i > 0 and not i & 1):



        # Trailing zeros after the trailing ones in 'n'

        c0 += 1



        i = i >> 1



    prev = n - (1 << c1) - (1 << (c0 - 1)) + 1



    return prev





def nearestNumbers(n):



    res = [0, 0]



    # Function to find the next smallest number

    res[0] = getNext(n)



    # Function to find the previous largest number

    res[1] = getPrev(n)



    return res

Given a positive integer ‘n’, your task is to find the next smallest integer and the previous largest integer having the exact number of ‘1’ bits set in their binary representation as ‘n’.

Example:

Note:

Input format:

Output format:

Constraints:

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer