current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 9 down vote favorite
1

I am working through analysis of algorithms class for the first time, and was wondering if anyone could assist with the below example. I believe I have solved it for an O(n) complexity, but was wondering if there is a better version that I am not thinking of O(logn)?

Let A= A[1] <= ... <= A[n+1] be a sorted array of n distinct integers, in which each integer is in the range [1...n+1]. That is, exactly one integer out of {1,...,n+1} is missing from A. Describe an efficeint algorithm to find the missing integer. Analyze the worst case complexity (number of accesses to array A) of your algorithm.

The solution I have is relatively simple, and I believe results in a worst case N complexity. Maybe I am over thinking the example, but is there a better solution?

My Solution

for(i = 1; i < n +1; i++) :
    if(A[i-1] > i) :
         return i

The logic behind this is since it is sorted, the first element must be 1, the second must be 2, and so on and so forth, until the element in the array is larger than the element it is supposed to be, indiciating an element was missed, return the element it should be and we have the missing one.

Is this correct logic? Is there a better way to go about it?

Thanks for reading and thanks in advance for the assistance.

share|improve this question
    
Yes. There is a better solution. Hint: do you REALLY have to look at every element in the array? –  aquinas 2 days ago
    
Would you please clean up your statement of the problem?  (1) If the A’s are distinct, that means they aren’t equal; so why not just say “A[1] < A[2] < …”?  (2) If { A[1], A[2], …, A[n+1] } ⊆ { 1, 2, …, n+1 }, then, ∀i, A[i] = i, and so there is no missing integer.  Your text says “n distinct integers”, so it can’t be A[1], A[2], …, A[n+1].  (3) Your problem statement says that the A’s begin with A[1], but your solution starts at A[0] (and, in the comments, you say that the array indices start at [0]). –  Scott 2 days ago

3 Answers 3

up vote 9 down vote accepted

This logic is certainly correct, but it is not fast enough to beat O(n) because you check every element.

You can do it faster by observing that if A[i]==i, then all elements at j < i are at their proper places. This observation should be sufficient to construct a divide-and-conquer approach that runs in O(log2n):

  • Check the element in the middle
  • If it's at the wrong spot, go left
  • Otherwise, go right

More formally, you are looking for a spot where A[i]==i and A[i+1]==i+2. You start with the interval at the ends of the array. Each probe at the middle of the interval shrinks the remaining interval twofold. At some point you are left with an interval of just two elements. The element on the left is the last "correct" element, while the element on the right is the first element after the missing number.

share|improve this answer
    
Let me take a shot at turning this into english based : - Pick the middle Value of 1....N - If A[i-1] (since valid integers start at 1, and array access starts at 0) != i - The missing element must be in the left - Pick the middle of 1 .... I-1 Rinse repeat until A[i-1] > i does this work? –  Busturdust 2 days ago
    
and if original pick was A[i-1] == i, then do the same to the right –  Busturdust 2 days ago
    
@Busturdust Yes, that's it. –  dasblinkenlight 2 days ago
    
Is A[i-1] > i really the termination clause? Because say if the element missing is the 1, all elements will be A[i-1] > i, and will terminate previously to getting to the first element. I think im missing something –  Busturdust 2 days ago
1  
@Busturdust You need to find a spot where A[i]==i and A[i+1]==i+2. You start with the interval at the ends of the array, and each probe at the middle of the interval shrinks the remaining interval twofold. At some point you are left with an interval of just two elements. The element on the left is the last "correct" element, while the element on the right is the first element after the missing number. –  dasblinkenlight 2 days ago
up vote 8 down vote

You can binary search for the first index i with A[i] > i. If the missing integer is k, then A[i] = i for i < k and A[i] = i + 1 for i >= k.

share|improve this answer
up vote 3 down vote

Sometimes the trick is to think of the problem in a different way.

In spirit, you are simply working with an array of boolean values; the entry at index n is the truth of a[n] > n.

Furthermore, this array begins with zero or more consecutive false, and the remaining entries are all true.

Your problem, now, is to find the index of the first instance of true in the (sorted) array of boolean values.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.