 New update is available. Click here to update.

# Nearest numbers with the same number of set bits

Last Updated: 22 Feb, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### 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
`````` ## Approach 1

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.