Problem

Submissions

Hints & solutions

Discuss

Nearest numbers with the same number of set bits

Easy

0/40

Average time to solve is 10m

Contributed by

9 upvotes

Asked in companies

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample input 1:

2
6
9

Sample output 1:

9 5
10 6

Explanation of sample input 1:

Test Case 1:

The binary representation of {5 = 0101, 6 = 0110, 7 = 0111, 8 = 1000, 9 = 1001}, here ‘9’ is the smallest integer greater than ‘6’ and ‘5’ is the largest integer smaller than ‘6’ having the exact number of ‘1’ bits set (i.e., two set bits) as that of ‘6’, so the answer is {9, 5}.


Test Case 2:

The binary representation of {6 = 0110, 7 = 0111, 8 = 1000, 9 = 1001, 10 = 1010}, here ‘10’ is the smallest integer greater than ‘9’ and ‘6’ is the largest integer smaller than ‘9’ having the exact number of ‘1’ bits set (i.e., two set bits) as that of ‘9’, so the answer is {10, 6}.

Sample input 2:

2
4
5

Sample output 2:

8 2
6 3

Hint 1

Hint 2

Can we use bit-manipulation on ‘n’ to solve this problem?

Approaches (3)

Approach 1

Approach 2

Approach 3

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.

Time Complexity

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

Space Complexity

O(1),

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

(100% EXP penalty)

Nearest numbers with the same number of set bits

Console