New update is available. Click here to update.

Last Updated: 22 Feb, 2021

Difficulty: Easy

```
‘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}.
```

```
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.
```

```
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’.
```

```
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.
```

```
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
```

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.

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.

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<<x’ (Here, ‘x >= 0’ and ‘2^x’ is in the valid integer range)**

SIMILAR PROBLEMS

Detect Odd

Posted: 15 Apr, 2022

Difficulty: Moderate

Detect Odd

Posted: 15 Apr, 2022

Difficulty: Moderate

Ninja And The Clan

Posted: 17 Apr, 2022

Difficulty: Moderate

Check whether K-th bit is set or not

Posted: 20 May, 2022

Difficulty: Easy

Check whether K-th bit is set or not

Posted: 20 May, 2022

Difficulty: Easy

Maximum Element

Posted: 21 Jul, 2022

Difficulty: Moderate

XOR DARE

Posted: 3 Sep, 2022

Difficulty: Moderate

Popular Interview Problems: