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)