Problem

Given an integer n, find the next biggest integer with the same number of 1-bits on. For example, given the number 6 (0110 in binary), return 9 (1001).

Examples

Example 1

1
2
3
4
5
6

Input: 6
Output: 9
Explanation:
6 in binary: 0110 (two 1-bits)
9 in binary: 1001 (two 1-bits)
9 is the next bigger integer with the same number of 1-bits as 6.

Example 2

1
2
3
4
5
6

Input: 3
Output: 5
Explanation:
3 in binary: 011 (two 1-bits)
5 in binary: 101 (two 1-bits)
5 is the next bigger integer with the same number of 1-bits as 3.

Example 3

1
2
3
4
5
6

Input: 12
Output: 17
Explanation:
12 in binary: 1100 (two 1-bits)
17 in binary: 10001 (two 1-bits)
17 is the next bigger integer with the same number of 1-bits as 12.

Example 4

1
2
3
4
5
6

Input: 7
Output: 11
Explanation:
7 in binary: 0111 (three 1-bits)
11 in binary: 1011 (three 1-bits)
11 is the next bigger integer with the same number of 1-bits as 7.

Example 5

1
2
3
4
5
6

Input: 1
Output: 2
Explanation:
1 in binary: 01 (one 1-bit)
2 in binary: 10 (one 1-bit)
2 is the next bigger integer with the same number of 1-bits as 1.

Solution

Method 1 - Bit Manipulation with Pattern Recognition

Intuition

To find the next bigger number with the same number of 1-bits, we need to rearrange the bits. The key insight is to find the rightmost 0-bit that has 1-bits to its right, flip it to 1, then rearrange the remaining bits to the right to get the smallest possible number. This involves finding the rightmost “01” pattern, flipping it to “10”, then moving all remaining 1-bits as far right as possible.

Approach

  1. Find the rightmost non-trailing zero (rightmost 0 with 1’s to its right)
  2. Flip this zero to 1 (this increases the number)
  3. Count the number of 1’s to the right of this position
  4. Clear all bits to the right of the flipped position
  5. Place (count-1) 1’s at the rightmost positions to minimize the result
  6. Handle edge case where no such arrangement exists (all 1’s are at the left)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    int nextBiggerSameBits(int n) {
        int c = n;
        int c0 = 0; // Count of trailing zeros
        int c1 = 0; // Count of ones to the right of trailing zeros
        
        // Count trailing zeros
        while (((c & 1) == 0) && c != 0) {
            c0++;
            c >>= 1;
        }
        
        // Count ones after trailing zeros
        while ((c & 1) == 1) {
            c1++;
            c >>= 1;
        }
        
        // No bigger number with same number of 1's
        if (c0 + c1 == 31 || c0 + c1 == 0) {
            return -1;
        }
        
        int p = c0 + c1; // Position of rightmost non-trailing zero
        n |= (1 << p);   // Flip the rightmost non-trailing zero
        n &= ~((1 << p) - 1); // Clear all bits to the right of p
        n |= (1 << (c1 - 1)) - 1; // Insert (c1-1) ones on the right
        
        return n;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func nextBiggerSameBits(n int) int {
    c := n
    c0 := 0 // Count of trailing zeros
    c1 := 0 // Count of ones to the right of trailing zeros
    
    // Count trailing zeros
    for (c&1) == 0 && c != 0 {
        c0++
        c >>= 1
    }
    
    // Count ones after trailing zeros
    for (c & 1) == 1 {
        c1++
        c >>= 1
    }
    
    // No bigger number with same number of 1's
    if c0+c1 == 31 || c0+c1 == 0 {
        return -1
    }
    
    p := c0 + c1              // Position of rightmost non-trailing zero
    n |= (1 << p)             // Flip the rightmost non-trailing zero
    n &= ^((1 << p) - 1)      // Clear all bits to the right of p
    n |= (1 << (c1 - 1)) - 1  // Insert (c1-1) ones on the right
    
    return n
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    public int nextBiggerSameBits(int n) {
        int c = n;
        int c0 = 0; // Count of trailing zeros
        int c1 = 0; // Count of ones to the right of trailing zeros
        
        // Count trailing zeros
        while (((c & 1) == 0) && c != 0) {
            c0++;
            c >>>= 1;
        }
        
        // Count ones after trailing zeros
        while ((c & 1) == 1) {
            c1++;
            c >>>= 1;
        }
        
        // No bigger number with same number of 1's
        if (c0 + c1 == 31 || c0 + c1 == 0) {
            return -1;
        }
        
        int p = c0 + c1; // Position of rightmost non-trailing zero
        n |= (1 << p);   // Flip the rightmost non-trailing zero
        n &= ~((1 << p) - 1); // Clear all bits to the right of p
        n |= (1 << (c1 - 1)) - 1; // Insert (c1-1) ones on the right
        
        return n;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def next_bigger_same_bits(self, n: int) -> int:
        c = n
        c0 = 0  # Count of trailing zeros
        c1 = 0  # Count of ones to the right of trailing zeros
        
        # Count trailing zeros
        while (c & 1) == 0 and c != 0:
            c0 += 1
            c >>= 1
        
        # Count ones after trailing zeros
        while (c & 1) == 1:
            c1 += 1
            c >>= 1
        
        # No bigger number with same number of 1's
        if c0 + c1 == 31 or c0 + c1 == 0:
            return -1
        
        p = c0 + c1              # Position of rightmost non-trailing zero
        n |= (1 << p)            # Flip the rightmost non-trailing zero
        n &= ~((1 << p) - 1)     # Clear all bits to the right of p
        n |= (1 << (c1 - 1)) - 1 # Insert (c1-1) ones on the right
        
        return n

Complexity

  • ⏰ Time complexity: O(log N), where N is the input number. We examine each bit position at most once
  • 🧺 Space complexity: O(1), only using constant extra space for counters and bit manipulation

Method 2 - Next Permutation Approach

Intuition

We can treat this as finding the next lexicographical permutation of the binary representation. Convert the number to a bit array, find the next permutation using the standard algorithm, then convert back to integer. This approach is more intuitive but less efficient than direct bit manipulation.

Approach

  1. Convert the integer to binary representation as a bit array
  2. Apply next permutation algorithm:
    • Find the rightmost bit that is smaller than the bit to its left
    • Find the smallest bit to the right that is larger than this bit
    • Swap these two bits
    • Reverse the bits to the right of the original position
  3. Convert the resulting bit array back to integer
  4. Handle edge cases where no next permutation exists

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
private:
    vector<int> getBits(int n) {
        vector<int> bits;
        if (n == 0) return {0};
        
        while (n > 0) {
            bits.push_back(n & 1);
            n >>= 1;
        }
        reverse(bits.begin(), bits.end());
        return bits;
    }
    
    int bitsToInt(const vector<int>& bits) {
        int result = 0;
        for (int bit : bits) {
            result = (result << 1) | bit;
        }
        return result;
    }
    
public:
    int nextBiggerSamePermutation(int n) {
        vector<int> bits = getBits(n);
        
        // Find next permutation
        int i = bits.size() - 2;
        while (i >= 0 && bits[i] >= bits[i + 1]) {
            i--;
        }
        
        if (i < 0) return -1; // No next permutation exists
        
        int j = bits.size() - 1;
        while (bits[j] <= bits[i]) {
            j--;
        }
        
        swap(bits[i], bits[j]);
        reverse(bits.begin() + i + 1, bits.end());
        
        return bitsToInt(bits);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

func getBits(n int) []int {
    if n == 0 {
        return []int{0}
    }
    
    var bits []int
    for n > 0 {
        bits = append([]int{n & 1}, bits...)
        n >>= 1
    }
    return bits
}

func bitsToInt(bits []int) int {
    result := 0
    for _, bit := range bits {
        result = (result << 1) | bit
    }
    return result
}

func nextBiggerSamePermutation(n int) int {
    bits := getBits(n)
    
    // Find next permutation
    i := len(bits) - 2
    for i >= 0 && bits[i] >= bits[i+1] {
        i--
    }
    
    if i < 0 {
        return -1 // No next permutation exists
    }
    
    j := len(bits) - 1
    for bits[j] <= bits[i] {
        j--
    }
    
    bits[i], bits[j] = bits[j], bits[i]
    
    // Reverse from i+1 to end
    for l, r := i+1, len(bits)-1; l < r; l, r = l+1, r-1 {
        bits[l], bits[r] = bits[r], bits[l]
    }
    
    return bitsToInt(bits)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class Solution {
    private List<Integer> getBits(int n) {
        List<Integer> bits = new ArrayList<>();
        if (n == 0) {
            bits.add(0);
            return bits;
        }
        
        while (n > 0) {
            bits.add(0, n & 1);
            n >>>= 1;
        }
        return bits;
    }
    
    private int bitsToInt(List<Integer> bits) {
        int result = 0;
        for (int bit : bits) {
            result = (result << 1) | bit;
        }
        return result;
    }
    
    public int nextBiggerSamePermutation(int n) {
        List<Integer> bits = getBits(n);
        
        // Find next permutation
        int i = bits.size() - 2;
        while (i >= 0 && bits.get(i) >= bits.get(i + 1)) {
            i--;
        }
        
        if (i < 0) return -1; // No next permutation exists
        
        int j = bits.size() - 1;
        while (bits.get(j) <= bits.get(i)) {
            j--;
        }
        
        Collections.swap(bits, i, j);
        Collections.reverse(bits.subList(i + 1, bits.size()));
        
        return bitsToInt(bits);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution:
    def get_bits(self, n: int) -> List[int]:
        if n == 0:
            return [0]
        
        bits = []
        while n > 0:
            bits.append(n & 1)
            n >>= 1
        return bits[::-1]
    
    def bits_to_int(self, bits: List[int]) -> int:
        result = 0
        for bit in bits:
            result = (result << 1) | bit
        return result
    
    def next_bigger_same_permutation(self, n: int) -> int:
        bits = self.get_bits(n)
        
        # Find next permutation
        i = len(bits) - 2
        while i >= 0 and bits[i] >= bits[i + 1]:
            i -= 1
        
        if i < 0:
            return -1  # No next permutation exists
        
        j = len(bits) - 1
        while bits[j] <= bits[i]:
            j -= 1
        
        bits[i], bits[j] = bits[j], bits[i]
        bits[i + 1:] = bits[i + 1:][::-1]
        
        return self.bits_to_int(bits)

Complexity

  • ⏰ Time complexity: O(log N), where N is the input number. Converting to bits and back takes O(log N), and next permutation is also O(log N)
  • 🧺 Space complexity: O(log N), for storing the bit array representation

Method 3 - Brute Force with Bit Counting

Intuition

A straightforward approach is to increment the number and check if it has the same number of 1-bits. While inefficient, this method is simple to understand and implement. We use built-in bit counting functions to compare the number of set bits.

Approach

  1. Count the number of 1-bits in the original number
  2. Start from n+1 and increment until we find a number with the same bit count
  3. Use built-in functions to count set bits efficiently
  4. Return the first number found that matches the criteria
  5. Handle potential overflow or infinite loop scenarios

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
private:
    int countBits(int n) {
        return __builtin_popcount(n);
    }
    
public:
    int nextBiggerBruteForce(int n) {
        int originalBits = countBits(n);
        
        for (int i = n + 1; i > n; i++) { // Check for overflow
            if (countBits(i) == originalBits) {
                return i;
            }
        }
        
        return -1; // No solution found (overflow case)
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func countBits(n int) int {
    count := 0
    for n > 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

func nextBiggerBruteForce(n int) int {
    originalBits := countBits(n)
    
    for i := n + 1; i > n; i++ { // Check for overflow
        if countBits(i) == originalBits {
            return i
        }
    }
    
    return -1 // No solution found (overflow case)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    private int countBits(int n) {
        return Integer.bitCount(n);
    }
    
    public int nextBiggerBruteForce(int n) {
        int originalBits = countBits(n);
        
        for (int i = n + 1; i > n; i++) { // Check for overflow
            if (countBits(i) == originalBits) {
                return i;
            }
        }
        
        return -1; // No solution found (overflow case)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def count_bits(self, n: int) -> int:
        return bin(n).count('1')
    
    def next_bigger_brute_force(self, n: int) -> int:
        original_bits = self.count_bits(n)
        
        i = n + 1
        while i > n:  # Check for overflow
            if self.count_bits(i) == original_bits:
                return i
            i += 1
        
        return -1  # No solution found (overflow case)

Complexity

  • ⏰ Time complexity: O(k * log N), where k is the difference between n and the answer, and log N for bit counting. In worst case, k can be exponential
  • 🧺 Space complexity: O(1), only using constant extra space

Notes

  • Method 1 is the most efficient solution using direct bit manipulation techniques
  • Method 2 provides a more intuitive approach using permutation concepts but with higher space complexity
  • Method 3 is the simplest to understand but highly inefficient for large numbers
  • The problem is essentially finding the next lexicographically larger binary string with the same number of 1’s
  • Edge cases include numbers where no larger number exists (like all 1’s followed by all 0’s)
  • For the bit manipulation approach, understanding the pattern of “01” → “10” transformation is crucial
  • The algorithm works by moving the leftmost 1-bit one position to the left and minimizing the remaining bits
  • This problem is commonly known as “Next Greater Element with Same Set Bits” in competitive programming
  • Method 1 is preferred for production code due to its O(1) space and O(log N) time complexity