Optimizing findMissingNumber algorithm to O(N)

Question

This problem is from Cracking the Code Interview:

An array A contains all the integers from Oto n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[ i ],"which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

I've put together a working solution, the remaining task is to optimize it to O(N) runtime. My solution:

1. Converts the binary number to decimal
2. Checks if the difference between i-1 and i elements > 1 to find the missing number
3. Converts the decimal back to binary by dividing repeatedly decimal % 2.

Additionally I've attempted to optimize by removing a separate for loop used for step # 2, that loops through the converted numbers.

Are there redundancies in the algo? How can I optimize this further?

const fetchNthBit = (bit: string, n) => {
    if (n <= 0) return 'Invalid index';
    return bit.charAt(bit.length - n);
}

const convertToBinary = (number) => { 
    let result = '';
    while (number > 0) { // O(N)
        const remainder = number % 2;
        number = Math.floor(number/2);
        result = remainder + result;
    }

    return result;
}

const findMissingNumber = function(arr) {
    let converted = [];
    let missingNumber = 0;
    // Convert numbers to binary 
    arr.forEach((binaryNumber, i) => {
        let binaryString = binaryNumber.toString();
        let nth = 0;
        let nthBaseValue = 0;
        while (nth < binaryString.length) {
            let nthBit = fetchNthBit(binaryString, binaryString.length - nth);
            if (nthBit === '1') {
                nthBaseValue += 2**(binaryString.length - 1 - nth);
            }
            nth++;
        }
        if (nthBaseValue - converted[i - 1] > 1) {
            missingNumber = convertToBinary(nthBaseValue - 1);
            return;
        }
        converted.push(nthBaseValue);
        nth = 0;
        nthBaseValue = 0;
    });
    
    return missingNumber ? missingNumber : 'No missing number.';
}

console.log('findMissingNumber: ', findMissingNumber([1, 10, 11, 101])); // 100
```

Answer 1

Query the least significant bit (LSB) of all the numbers and split them into two sets $E, O$ where $E$ contains the even numbers (the least significant bit is 0) and $O$ contains the odd numbers.

Now xor together all these bits. If the result matches the LSB of $\sum_{i=0}^n i = \frac{i(i+1)}{2}$ then the missing number must be even (its LSB is 0), and you can apply this algorithm recursively to find the missing number between $0$ and $\lfloor n/2 \rfloor$ among all the numbers on $E$ without their LSBs.

Otherwise the LSB of the missing number is $1$ and you can apply this algorithm recursively on $O$.

The overall time spent is described by the recurrence equation $T(n) = T(\lfloor n/2 \rfloor) + O(n)$ which has solution $T(n)=O(n)$.