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.

Thanks
SRK

srk <kumarsr@gmail.com> wrote:

Homework ? Then sorting and iterating the array until you find the
missing number is not the answer you're looking for, is it ?

--
:wq
^X^Cy^K^X^C^C^C^C

On May 29, 4:06*pm, Ico <use...@zeev.nl> wrote:
Definately I am not looking for O(n2) complexity. I want max O(n) or
O(nlogn) complexity.

On Thu, 29 May 2008 03:10:32 -0700 (PDT), srk <kumarsr@gmail.com>
wrote:


The numbers from 1 to n add up to (n * (n + 1)) / 2.

The difference is the missing number.

rossum

SRK <kumarsr@gmail.com> wrote:
Enough sorting algorithms are possible in O(nlogn) time. But you are
probably not allowed to sort, are you ?

The anwer to your assignment is just a trick, no sorting is needed. Try
thinking the other way around: is there something you can say about the
set of numbers [1..n] that you can use to tell if one of those numbers
was missing. For example, can you tell in advance what the sum of all
numbers [1..n] is, without actually adding them all up ?

--
:wq
^X^Cy^K^X^C^C^C^C

rossum <rossum48@coldmail.com> wrote:
Yes, now we all know you know the trick. Thanks for doing his homework,
I guess he really learned something today

--
:wq
^X^Cy^K^X^C^C^C^C

On Thu, 29 May 2008 04:27:47 -0700 (PDT)
SRK <kumarsr@gmail.com> wrote:

Then it will require sum thought.

--
C:>WIN | Directable Mirror Arrays
The computer obeys and wins. | A better way to focus the sun
You lose and Bill collects. | licences available see
| http://www.sohara.org/

Ico wrote:
I fail to understand how that is relevant to the problem in question.
Yes, being able to calculate the sum of integers 1-n without doing an
explicit loop is faster, but it doesn't change the O(n) complexity of
the requested algorithm.

Juha Nieminen <nospam@thanks.invalid> wrote:
See rossum's reply, he explains the algorithm there.

--
:wq
^X^Cy^K^X^C^C^C^C

On May 29, 6:10 am, srk <kuma...@gmail.com> wrote:
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.

On Thu, 29 May 2008 12:39:08 +0100, rossum wrote:

An other option would be to *multiply* all the entries, and divide n! by
the sum ;-)

AvK

by the product :-)

Stephen Howe

On May 29, 4:39*am, rossum <rossu...@coldmail.com> wrote:
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?

user923005 wrote:
Read the first paragraph quoted, the original statement of the
problem.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

** Posted from http://www.teranews.com **

On May 29, 4:45*pm, CBFalconer <cbfalco...@yahoo.com> wrote:
The original problem statement makes not statement about the
initialization of the array. In no place does it say that all the
initial entries are zero.

user923005 said:

<snip>

On this occasion, I recommend (and I must admit that this comes as a
surprise) that you listen to Chuck. The original problem statement
nullifies your objections completely. Here it is again:

"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."

From the phrase "which number is missing" we deduce that precisely one
number is missing. If duplicates were allowed (and also if "number" were
allowed to include non-integers, which I mention only in an attempt at
completeness), more than one number might be missing. Since it is known
that precisely one number is missing, we deduce that duplicates are not
allowed. Furthermore, because we know that only one number is missing and
there are n numbers (all in the range 1 to n) originally, we know that
there are n-1 numbers present. Since the array has size n-1, we can
legitimately and correctly deduce that it is entirely populated with n-1
unique numbers in the range 1 to n.

"The trick" is therefore guaranteed to work provided only that n(n-1)/2
does not exceed the maximum possible value for a number on the host
system.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

On Thu, 29 May 2008 19:45:59 -0400, CBFalconer
<cbfalconer@yahoo.com> wrote:

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@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

Richard wrote:
) "The trick" is therefore guaranteed to work provided only that n(n-1)/2
) does not exceed the maximum possible value for a number on the host
) system.

Or if your host system can do modulo-X (*) math properly.
Note that you will have to be quite precise in how you calculate n(n-1)/2.

*) X being, for example, 2^32

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

On Fri, 30 May 2008 04:25:42 +0000, Richard Heathfield
<rjh@see.sig.invalid> wrote:

That won't quite do. Your points are well taken and yet there is
a problem. The original states that the numbers from 1 to n are
being placed in the array randomly. Ergo the n-1 locations
somehow hold n numbers. This implies in turn that at least one
location in the array can hold more than one number. This would
be a problem for ordinary arrays but the problem statement
clearly implies that this is a special sort of array. Since all
n numbers are present (somehow!) it follows that "missing" does
not have its customary meaning of absent. What precisely that
meaning might be is open to question. An obvious answer is a
numerological interpretation, i.e., "missing" = 13+9+19+19+9+14+7
= 90, but that is not enough. Evidently some number is 90 in
disguise and we have to find out which one it is. Since we have
already established that there is a location in the array that
has two elements the question might be to be to find that
location with two elements. How to do this is problematic. My
thought is that if we can't see 90 on the front side of the array
we look at its back side.

The moral of the story is that if you don't state the problem
carefully you can get some really weird solutions.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

On Fri, 30 May 2008 05:21:46 +0000 (UTC), Willem
<willem@stack.nl> wrote:

Better yet, do the arithmetic module n+1. Note that n(n-1)/2 = 1
modulo n+1. If k is the missing number and S is the sum of the
n-1 numbers modulo n+1, then k = n+2-S.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.