Recursive algorithm problem(missing number)

Question

So I have an array A[1:n] which contains random unique numbers from 1 to n+1(including n+1). The task is to find the missing number. Usually you just make an additional array B[1:n+1] and mark each present number in array A as 1 in array B. BUT in this problem you each number in array A is given in binary code as a string and I can access elements of A only by j-th symbol in a i-th string The goal is to come up with an algorithm with complexity O(n)

My ideas: I came up with a merge sort based algorithm, which would sort every string according its first number in binary code. But the complexity is O(nlgn)

Answer 1

As discussed in the comments, if elements of A can only be accessed bit-by-bit then no O(n) solution is going to be possible, since all bits have to be read, and there are log n bits in each number. The best that can be done is O(n log n).

That said, if the array contains n elements from the range 1 to n+1, with exactly one value missing, the missing value can be found by taking the sum of the array and comparing it to the sum to n+1, given by the standard formula, (n+1)(n+2)/2.

int n = 3;
String[] arr = {"001", "010", "100"};

int sum = 0;
for(int i=0; i<arr.length; i++) 
    for(int j=0, v=1; j<arr[i].length(); j++, v*=2)
        if(arr[i].charAt(j) == '1') sum += v;

int m = (n+1)*(n+2)/2 - sum;

System.out.println("Missing: " + m);

Output:

Missing: 3