Re: searching for missing element in an array
- From: cri@xxxxxxxx (Richard Harter)
- Date: Fri, 30 May 2008 04:58:23 GMT
On Thu, 29 May 2008 19:45:59 -0400, CBFalconer
<cbfalconer@xxxxxxxxx> wrote:
user923005 wrote:
rossum <rossu...@xxxxxxxxxxxx> wrote:
srk <kuma...@xxxxxxxxx> wrote:
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.
Total all the numbers in the array.
The numbers from 1 to n add up to (n * (n + 1)) / 2.
The difference is the missing number.
What happens if you have some number twice? e.g.: 1,2,2,4,5
What happens if the array was initialized to all -1 values? Do
we know that a zero is stored in the slot of the missing number?
Read the first paragraph quoted, the original statement of the
problem.
I had the same thought; however the original statement is
ambiguous. The phrasing does not forbid 1,2,2,4,5 etc. What
precisely is meant by the numbers 1 to n are being placed in
array randomly"? It could mean that each element in the array is
a random number chosen from 1...n.
Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.
- References:
- searching for missing element in an array
- From: srk
- Re: searching for missing element in an array
- From: rossum
- Re: searching for missing element in an array
- From: user923005
- Re: searching for missing element in an array
- From: CBFalconer
- searching for missing element in an array
- Prev by Date: Re: In-place algorithm
- Next by Date: Re: searching for missing element in an array
- Previous by thread: Re: searching for missing element in an array
- Next by thread: Re: searching for missing element in an array
- Index(es):
Relevant Pages
|
