# Smallest sparse number greater than or equal to N.

By | June 20, 2023

We say a number is sparse if there are no adjacent ones in its binary representation. For example, 21 (10101) is sparse, but 22 (10110) is not. For a given input N, find the smallest sparse number greater than or equal to N. Do this in faster than O(N log N) time. Solution in Java and Javascript

Java

```public class SmallestSparseNumber {
public static int findSmallestSparseNumber(int N) {
String binaryRep = Integer.toBinaryString(N);
int result = N;
int prevBit = -1;

for (int i = 0; i < binaryRep.length(); i++) {
int currentBit = Character.getNumericValue(binaryRep.charAt(i));

if (currentBit == 1 && prevBit == 1) {
// Set all bits from current position to rightmost bit to 0
result &= ~((1 << (binaryRep.length() - i)) - 1);

// Set the next bit after the rightmost bit to 1
result |= (1 << (binaryRep.length() - i - 1));

// Update prevBit to the new value at the current position
prevBit = 1;
} else {
// Update prevBit to the new value at the current position
prevBit = currentBit;
}
}

return result;
}

public static void main(String[] args) {
int N = 22;
int result = findSmallestSparseNumber(N);
System.out.println(result);  // Output: 32
}
}

```

Javascript

```function findSmallestSparseNumber(N) {
const binaryRep = N.toString(2);
let result = N;
let prevBit = -1;

for (let i = 0; i < binaryRep.length; i++) {
const currentBit = parseInt(binaryRep.charAt(i));

if (currentBit === 1 && prevBit === 1) {
// Set all bits from current position to rightmost bit to 0
result &= ~((1 << (binaryRep.length - i)) - 1);

// Set the next bit after the rightmost bit to 1
result |= 1 << (binaryRep.length - i - 1);

// Update prevBit to the new value at the current position
prevBit = 1;
} else {
// Update prevBit to the new value at the current position
prevBit = currentBit;
}
}

return result;
}

const N = 22;
const result = findSmallestSparseNumber(N);
console.log(result);  // Output: 32

```

Explanation

1. The function `findSmallestSparseNumber` takes an input integer `N` and converts it to its binary representation using `Integer.toBinaryString(N)` in Java or `N.toString(2)` in JavaScript.
2. The binary representation is stored in the `binaryRep` variable.
3. The variable `result` is initialized with the value of `N`. This variable will hold the current number being processed and adjusted to make it sparse.
4. The variable `prevBit` is initialized with -1. It keeps track of the previous bit encountered during the iteration.
5. The function iterates through each bit from left to right in the binary representation of `N`.
6. For each bit, the current bit value is obtained using `Character.getNumericValue(binaryRep.charAt(i))` in Java or `parseInt(binaryRep.charAt(i))` in JavaScript.
7. If the current bit is 1 and the previous bit is also 1, it means there are adjacent ones in the binary representation.
8. In this case, the algorithm performs the following steps to adjust the number and make it sparse:
• It sets all the bits from the current position to the rightmost bit to 0 by performing a bitwise AND operation with the complement of a bitmask.
• It sets the next bit after the rightmost bit to 1 by performing a bitwise OR operation with a bitmask.
• It updates the `prevBit` variable to 1, indicating the new value at the current position.
9. If the current bit is 0 or the previous bit is 0, it means there are no adjacent ones, and the algorithm updates the `prevBit` variable to the new value at the current position.
10. After processing all the bits, the algorithm returns the final value stored in the `result` variable, which represents the smallest sparse number greater than or equal to `N`.

The algorithm eliminates the need to check all numbers individually, resulting in a faster solution with a time complexity of O(log N) compared to the O(N log N) requirement.