Re: searching for missing element in an array
- From: cbcurl <cbcurl@xxxxxxxxx>
- Date: Thu, 29 May 2008 07:29:00 -0700 (PDT)
On May 29, 6:10 am, srk <kuma...@xxxxxxxxx> wrote:
Hi,
Suppose we have n numbers(from 1 to n) and there is an array of size
n-1. How can we find, which number is missing from the array if
numbers 1 to n are being placed in array randomly.
We used this as an interview question at my previous job.
The standard trick answer is to add the numbers of and subtract from
n(n-1)/2, but of course that assumes that integers cannot overflow and
it doesn't scale to finding more than one missing number.
A more general O(n) solution is to create a bit-vector of length n
initialized to zero, set the corresponding bit for each number in the
array in one pass and then do another pass to look for the bits that
have not been set.
.
- References:
- Prev by Date: Re: searching for missing element in an array
- Next by Date: Re: simple transport protocol
- Previous by thread: Re: searching for missing element in an array
- Next by thread: Re: String matching & linear programming...
- Index(es):
Relevant Pages
|
