Smallest sparse number greater than or equal to N

Problem

We say a number is sparse if there are no adjacent ones in its binary representation.

Do this in faster than O(N log N) time.

Examples

Example 1

Input: N = 22
Output: 32
Explanation: Binary representation of 22 is `10110`, which is not sparse. The next sparse number is `32` (binary `100000`), which has no adjacent ones.

Example 2

Input: N = 37
Output: 37
Explanation: Binary representation of 37 is `100101`, which is sparse because there are no adjacent ones. Hence, the smallest sparse number greater than or equal to 37 is 37 itself.

Solution

Method 1 - Bit manipulation

Key points:

1. Binary Representation: Observing the binary representation of a number makes it straightforward to identify whether it is sparse.
2. Non-Adjoining Ones: If adjacent ones exist, they violate the sparse condition and necessitate corrections to the binary digits.
3. Modifying Bits: To efficiently find the next sparse number greater than or equal to N, manipulate the binary digits of N to eliminate consecutive ones.
4. Backtracking Propagation: If consecutive ones are found, reset specific bits and propagate changes leftward to ensure higher-order bits maintain sparsity.

Approach

1. Binary Traversal:
   • Start with the binary representation of the number and scan for consecutive ones.
2. Modification:
   • When consecutive ones appear, reset violating bits by rounding the number upwards.
   • Propagate adjustments leftward to ensure the entire number remains sparse.
3. Efficiency:
   • By leveraging bit manipulation, the process avoids incrementing N step-by-step, achieving faster-than- O(N log N) runtime.

Code

Java

class Solution {

    public int smallestSparse(int n) {
        // Store the binary digits of the number
        int[] binary = new int[32];
        int index = 0;
        int num = n;

        // Convert to binary and store digits in an array
        while (num > 0) {
            binary[index++] = num % 2;
            num /= 2;
        }

        // Ensure sparsity
        boolean changed = false;
        for (int i = 1; i < index; i++) {
            if (binary[i] == 1 && binary[i - 1] == 1) {
                binary[i] = 0;
                changed = true;
                for (int j = i + 1; j < 32; j++) {
                    binary[j] = 0;
                }
                num = 0;
                for (int k = 0; k < index; k++) {
                    num = num + binary[k] * (1 << k);
                }
                break;
            }
        }
        return num;
    }
}

Python

class Solution:
    def smallestSparse(self, n: int) -> int:
        # Convert the integer to a list of binary digits
        binary = list(bin(n)[2:])
        length = len(binary)

        # Flag indicating whether the number was changed
        changed = False

        # Traverse the binary representation to identify adjacent ones
        for i in range(length - 1):
            if binary[i] == '1' and binary[i + 1] == '1':
                # Fix the first "1" and reset the right-side bits
                changed = True
                binary[i + 1] = '0'
                for j in range(i + 2, length):
                    binary[j] = '0'

                # Convert back to an integer
                result = int("".join(binary), 2)
                return self.smallestSparse(result)
        
        # If no changes, the number is already sparse
        return int("".join(binary), 2)

Complexity

• ⏰ Time complexity: O(n log n). The algorithm inspects and modifies bits iteratively, moving leftward as needed. Given k as the number of bits of N, the complexity is O(k) because we process at most all bits of N.
• 🧺 Space complexity: O(1). The algorithm utilises constant auxiliary space for bit manipulation.