f

#### MISSING NUMBER

* suppose you have a set of unsorted numbers from 1 to N (a big
number, say 1 million). One number is missing, how to find that
missing number most efficiently?

Adding the number then subtract N(N+1)/2 may not be possible since the
number could be too big to store.

 0
1/10/2009 6:55:56 PM
comp.programming 11491 articles. 2 followers.

23 Replies
500 Views

Similar Articles

[PageSpeed] 48

"Tagore" <c.lang.myself@gmail.com> wrote in message
> * suppose you have a set of unsorted numbers from 1 to N (a big
> number, say 1 million). One number is missing, how to find that
> missing number most efficiently?
>
> Adding the number then subtract N(N+1)/2 may not be possible since the
> number could be too big to store.

How do you want to calculate the effeciency?
Time? Memory? (Both?)
If you may use O(n) memory then there is an easy O(n) algorithm to find the
number.
There may still be such an algorithm if you may not use so much memory but I
can't think of one right now.


 0
1/10/2009 7:20:50 PM
On Sat, 10 Jan 2009 10:55:56 -0800 (PST), Tagore
<c.lang.myself@gmail.com> wrote:

>* suppose you have a set of unsorted numbers from 1 to N (a big
>number, say 1 million). One number is missing, how to find that
>missing number most efficiently?
>
>Adding the number then subtract N(N+1)/2 may not be possible since the
>number could be too big to store.

The obvious way is to add the numbers modulo N.  There is a
little trick.  If N is odd sum(1..N) modulo N = 0; if N is even
it is N/2.  For example, if N is 1000000 and the missing number
is 489733 the sum in module 1000000 arithmetic is 10267.

You can also precompute what the result of xor'ing all of the
numbers from 1 to N would be and then xor that with xor'ing of
all of the given numbers.  The precomputing can be done on a bit
by bit basis but I'm too lazy to spell out the details.

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.

 0
cri (1432)
1/10/2009 7:42:49 PM
On Jan 10, 12:55=EF=BF=BDpm, Tagore <c.lang.mys...@gmail.com> wrote:
> * suppose you have a set of unsorted numbers from 1 to N (a big
> number, say 1 million). One number is missing, how to find that
> missing number most efficiently?
>
> Adding the number then subtract N(N+1)/2 may not be possible since the
> number could be too big to store.

Use a math library where "too big to store" isn't
an issue.

 0
mensanator (1210)
1/10/2009 8:06:58 PM
Richard Harter wrote:
> You can also precompute what the result of xor'ing all of the
> numbers from 1 to N would be

Out of curiosity: Is there any faster way of doing that other than
making a loop from 1 to N and xorring the loop counter?

I was thinking something along the lines of: If N modulo 4 is 1 or 2,
you know the least-significant bit of the xor will be 1, else it will be
0. Could similar rules be developed for all the other bits as well?

 0
nospam270 (2948)
1/10/2009 8:12:43 PM
Mensanator wrote:
> On Jan 10, 12:55�pm, Tagore <c.lang.mys...@gmail.com> wrote:
>> * suppose you have a set of unsorted numbers from 1 to N (a big
>> number, say 1 million). One number is missing, how to find that
>> missing number most efficiently?
>>
>> Adding the number then subtract N(N+1)/2 may not be possible since the
>> number could be too big to store.
>
> Use a math library where "too big to store" isn't
> an issue.

He wanted the most efficient way of doing that, and using a library
for numbers of unlimited size is certainly *not* the most efficient way
of doing what he wants.

 0
nospam270 (2948)
1/10/2009 8:14:04 PM
On Sat, 10 Jan 2009 12:06:58 -0800 (PST), Mensanator
<mensanator@aol.com> wrote:

>On Jan 10, 12:55=EF=BF=BDpm, Tagore <c.lang.mys...@gmail.com> wrote:
>> * suppose you have a set of unsorted numbers from 1 to N (a big
>> number, say 1 million). One number is missing, how to find that
>> missing number most efficiently?
>>
>> Adding the number then subtract N(N+1)/2 may not be possible since the
>> number could be too big to store.
>
>Use a math library where "too big to store" isn't
>an issue.

In what way is this "most efficiently"?  Not, I fancy, in terms
of efficiency of computer space or time.  Not even in terms of
programmer time if you take into account the work of linkin in a
library?  Now if only you had said, use a language with bignums,
you could make a case for efficient use of programmer effort, but
as it is ...

Be that as it may, this is a programming puzzle rather than a
real problem as such.  Traditionally, "cheating" is a legitimate
response, where "cheating" means an answer that relies on a
lawyerly reading of the terms of the puzzle.  But in the context
of answering puzzles, even cheating must be fair.

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.

 0
cri (1432)
1/10/2009 8:31:01 PM
On Jan 10, 10:55=A0am, Tagore <c.lang.mys...@gmail.com> wrote:
> * suppose you have a set of unsorted numbers from 1 to N (a big
> number, say 1 million). One number is missing, how to find that
> missing number most efficiently?
>
> Adding the number then subtract N(N+1)/2 may not be possible since the
> number could be too big to store.

You only require that you calculate the sum modulo K, where K > N.
I.e., if the number is too big, go ahead and let it wrap around.
There are complicated ways of computing N(N+1)/2 doing this through
direct calculation, but why bother:

numSum =3D 0;
inputSum =3D 0;
for (i=3D0; i < N-1; i++) {
numSum +=3D i;
inputSum +=3D array[i];
}
return (numSum + N-1) - inputSum;

In any 2s complement system the above will worth without issue,
regardless of overflow issues.  Another way is to use a xor sum rather
than a direct sum:

numSum =3D 0;
inputSum =3D 0;
for (i=3D0; i < N-1; i++) {
numSum ^=3D i;
inputSum ^=3D array[i];
}
return numSum ^ (N-1) ^ inputSum;

--
Paul Hsieh
http://www.pobox.com/~qed/


 0
websnarf (1153)
1/10/2009 9:59:07 PM
cri@tiac.net (Richard Harter) writes:

> On Sat, 10 Jan 2009 10:55:56 -0800 (PST), Tagore
> <c.lang.myself@gmail.com> wrote:
>
>>* suppose you have a set of unsorted numbers from 1 to N (a big
>>number, say 1 million). One number is missing, how to find that
>>missing number most efficiently?
>>
>>Adding the number then subtract N(N+1)/2 may not be possible since the
>>number could be too big to store.
>
> The obvious way is to add the numbers modulo N.  There is a
> little trick.  If N is odd sum(1..N) modulo N = 0; if N is even
> it is N/2.  For example, if N is 1000000 and the missing number
> is 489733 the sum in module 1000000 arithmetic is 10267.
>
> You can also precompute what the result of xor'ing all of the
> numbers from 1 to N would be and then xor that with xor'ing of
> all of the given numbers.  The precomputing can be done on a bit
> by bit basis but I'm too lazy to spell out the details.

That's smart.

But anyways, the memory size needed to store N(N+1)/2 is insignificant
compared to the memory size needed to store the numbers from 1 to N
(minus one).  For example, for N=1e6, the size to store N(N+1)/2 is 2
millionth of the size to store the other numbers.

--
__Pascal Bourguignon__

 0
pjb (7869)
1/10/2009 10:12:28 PM
"Juha Nieminen" <nospam@thanks.invalid> wrote in message
news:%i7al.210$nD1.180@read4.inet.fi... > Richard Harter wrote: >> You can also precompute what the result of xor'ing all of the >> numbers from 1 to N would be > > Out of curiosity: Is there any faster way of doing that other than > making a loop from 1 to N and xorring the loop counter? > > I was thinking something along the lines of: If N modulo 4 is 1 or 2, > you know the least-significant bit of the xor will be 1, else it will be > 0. Could similar rules be developed for all the other bits as well? The modulo 4 pattern is as such: 0, 1, 3, 0, 4, 1, 7, 0, 8, 1, B, 0, C, 1, F, 0 10, 1, 13, 0 14, 1, 17, 0 18, 1, 1B, 0 etc Looks like a closed-form formula shouldn't be too hard to find   0 1/10/2009 10:40:21 PM Richard Harter wrote: > Tagore <c.lang.myself@gmail.com> wrote: > >> suppose you have a set of unsorted numbers from 1 to N (a big >> number, say 1 million). One number is missing, how to find that >> missing number most efficiently? >> >> Adding the number then subtract N(N+1)/2 may not be possible >> since the number could be too big to store. > > The obvious way is to add the numbers modulo N. There is a > little trick. If N is odd sum(1..N) modulo N = 0; if N is even > it is N/2. For example, if N is 1000000 and the missing number > is 489733 the sum in module 1000000 arithmetic is 10267. > > You can also precompute what the result of xor'ing all of the > numbers from 1 to N would be and then xor that with xor'ing of > all of the given numbers. The precomputing can be done on a bit > by bit basis but I'm too lazy to spell out the details. That's ingenious. -- [mail]: Chuck F (cbfalconer at maineline dot net) [page]: <http://cbfalconer.home.att.net> Try the download section.   0 cbfalconer (19194) 1/11/2009 1:02:31 AM On Jan 10, 2:31=EF=BF=BDpm, c...@tiac.net (Richard Harter) wrote: > On Sat, 10 Jan 2009 12:06:58 -0800 (PST), Mensanator > > <mensana...@aol.com> wrote: > >On Jan 10, 12:55=3DEF=3DBF=3DBDpm, Tagore <c.lang.mys...@gmail.com> wrot= e: > >> * suppose you have a set of unsorted numbers from 1 to N (a big > >> number, say 1 million). One number is missing, how to find that > >> missing number most efficiently? > > >> Adding the number then subtract N(N+1)/2 may not be possible since the > >> number could be too big to store. > > >Use a math library where "too big to store" isn't > >an issue. > > In what way is this "most efficiently"? The OP suggested an algorithm, but claimed that it could be too big to store. I was addressing whether said algorithm could work at all, not whether it was most efficient. >=EF=BF=BDNot, I fancy, in terms of efficiency of computer space or time. = =EF=BF=BD Is there an algorithm that DOESN'T require storing the 999999 numbers? > Not even in terms of > programmer time if you take into account the work of linkin in a > library? =EF=BF=BD Come on! How hard can that be? Actually, I already know. For your benefit, its: #include <gmp.h> Lotta work, that is, eh? > Now if only you had said, use a language with bignums, Oh, like Python? Won't even have to do an import. But technically, you're correct. But how much effort are you going to save when you optimze 0.001% of the problem? > you could make a case for efficient use of programmer effort, but > as it is ... It's pretty hard to see how ANYTHING could be more efficient in terms of programmer effort. >>> big =3D range(1,1000001) >>> n =3D random.choice(big) >>> big.pop(n) >>> s =3D sum(big) >>> soi =3D (1000000**2 + 1000000)/2 >>> soi-s 151072L Note, the first three lines are the given, the solution only takes the last three lines. > > Be that as it may, this is a programming puzzle rather than a > real problem as such. =EF=BF=BD So? It was the OP's algorithm, not mine. All I'm doing is pointing out that there is no impediment to said algorithm. > Traditionally, "cheating" is a legitimate > response, where "cheating" means an answer that relies on a > lawyerly reading of the terms of the puzzle. =EF=BF=BDBut in the context > of answering puzzles, even cheating must be fair. Fine, when it's posted that only native C code, with it's 32-bit integers are allowed. But that wasn't said. > > Richard Harter, c...@tiac.nethttp://home.tiac.net/~cri,http://www.varinom= a.com > Save the Earth now!! > It's the only planet with chocolate.   0 mensanator (1210) 1/11/2009 4:00:34 AM On Jan 10, 2:14=EF=BF=BDpm, Juha Nieminen <nos...@thanks.invalid> wrote: > Mensanator wrote: > > On Jan 10, 12:55 pm, Tagore <c.lang.mys...@gmail.com> wrote: > >> * suppose you have a set of unsorted numbers from 1 to N (a big > >> number, say 1 million). One number is missing, how to find that > >> missing number most efficiently? > > >> Adding the number then subtract N(N+1)/2 may not be possible since the > >> number could be too big to store. > > > Use a math library where "too big to store" isn't > > an issue. > > =EF=BF=BD He wanted the most efficient way of doing that, and using a lib= rary > for numbers of unlimited size is certainly *not* the most efficient way > of doing what he wants. I didn't say it was. See my reply to RH.   0 mensanator (1210) 1/11/2009 4:02:45 AM "Tagore" <c.lang.myself@gmail.com> wrote in message news:2d6e8332-d116-4d55-a6e2-ca0e204a63c5@n33g2000pri.googlegroups.com... > * suppose you have a set of unsorted numbers from 1 to N (a big > number, say 1 million). One number is missing, how to find that > missing number most efficiently? > > Adding the number then subtract N(N+1)/2 may not be possible since the > number could be too big to store. Use double precsion arithmetic.   0 robin_v (2737) 1/12/2009 1:31:22 AM Mensanator wrote: > Juha Nieminen <nos...@thanks.invalid> wrote: >> Mensanator wrote: >>> Tagore <c.lang.mys...@gmail.com> wrote: >>> >>>> suppose you have a set of unsorted numbers from 1 to N (a big >>>> number, say 1 million). One number is missing, how to find >>>> that missing number most efficiently? >>>> >>>> Adding the number then subtract N(N+1)/2 may not be possible >>>> since the number could be too big to store. >>> >>> Use a math library where "too big to store" isn't an issue. >> >> He wanted the most efficient way of doing that, and using a >> library for numbers of unlimited size is certainly *not* the >> most efficient way of doing what he wants. > > I didn't say it was. See my reply to RH. Actually, for 10e6 numbers, you don't need 10e6 4 byte number storage, you only need 10e6 bits, which will always fit in 125k bytes (or less, for bigger bytes). All you have to record is seen vs not-seen. At completion, scan the bit array to find the missing beasts. You can also do some ingenious optimizations. Shouldn't take much longer than the file reading time. -- [mail]: Chuck F (cbfalconer at maineline dot net) [page]: <http://cbfalconer.home.att.net> Try the download section.   0 cbfalconer (19194) 1/12/2009 1:38:16 AM robin wrote: > "Tagore" <c.lang.myself@gmail.com> wrote: > >> suppose you have a set of unsorted numbers from 1 to N (a big >> number, say 1 million). One number is missing, how to find that >> missing number most efficiently? >> >> Adding the number then subtract N(N+1)/2 may not be possible >> since the number could be too big to store. > > Use double precsion arithmetic. To see what you need, compute (N * N + N + 1) and divide it by 2. If N is roughly 10e6 the result will be roughly 10e12. -- [mail]: Chuck F (cbfalconer at maineline dot net) [page]: <http://cbfalconer.home.att.net> Try the download section.   0 cbfalconer (19194) 1/12/2009 3:56:09 AM On Sat, 10 Jan 2009 23:12:28 +0100, pjb@informatimago.com (Pascal J. Bourguignon) wrote: >cri@tiac.net (Richard Harter) writes: > >> On Sat, 10 Jan 2009 10:55:56 -0800 (PST), Tagore >> <c.lang.myself@gmail.com> wrote: >> >>>* suppose you have a set of unsorted numbers from 1 to N (a big >>>number, say 1 million). One number is missing, how to find that >>>missing number most efficiently? >>> >>>Adding the number then subtract N(N+1)/2 may not be possible since the >>>number could be too big to store. >> >> The obvious way is to add the numbers modulo N. There is a >> little trick. If N is odd sum(1..N) modulo N = 0; if N is even >> it is N/2. For example, if N is 1000000 and the missing number >> is 489733 the sum in module 1000000 arithmetic is 10267. >> >> You can also precompute what the result of xor'ing all of the >> numbers from 1 to N would be and then xor that with xor'ing of >> all of the given numbers. The precomputing can be done on a bit >> by bit basis but I'm too lazy to spell out the details. > >That's smart. > >But anyways, the memory size needed to store N(N+1)/2 is insignificant >compared to the memory size needed to store the numbers from 1 to N >(minus one). For example, for N=1e6, the size to store N(N+1)/2 is 2 >millionth of the size to store the other numbers. If you are reading the numbers from a file you don't need to store the numbers. 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.   0 cri (1432) 1/12/2009 4:52:08 AM On Sat, 10 Jan 2009 20:12:43 GMT, Juha Nieminen <nospam@thanks.invalid> wrote: >Richard Harter wrote: >> You can also precompute what the result of xor'ing all of the >> numbers from 1 to N would be > > Out of curiosity: Is there any faster way of doing that other than >making a loop from 1 to N and xorring the loop counter? > > I was thinking something along the lines of: If N modulo 4 is 1 or 2, >you know the least-significant bit of the xor will be 1, else it will be >0. Could similar rules be developed for all the other bits as well? I'm going to let you work out the formula for yourself. The key observations are (a) if the difference between the number of 0's and 1's is even the final xor is 0, otherwise it is odd, (b) in bit position k (starting the position number with 0) there are alternating sequences of 2^k 0's and 2^k 1's in the sequence of integers, (c) in consequence of (b) we only need to look at N modulo 2^(k+1), and (d) we only need to know whether N modulo 2^(k+1) is odd or even. 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.   0 cri (1432) 1/12/2009 5:00:11 AM On Mon, 12 Jan 2009 05:00:11 GMT, cri@tiac.net (Richard Harter) wrote: >On Sat, 10 Jan 2009 20:12:43 GMT, Juha Nieminen ><nospam@thanks.invalid> wrote: > >>Richard Harter wrote: >>> You can also precompute what the result of xor'ing all of the >>> numbers from 1 to N would be >> >> Out of curiosity: Is there any faster way of doing that other than >>making a loop from 1 to N and xorring the loop counter? >> >> I was thinking something along the lines of: If N modulo 4 is 1 or 2, >>you know the least-significant bit of the xor will be 1, else it will be >>0. Could similar rules be developed for all the other bits as well? > >I'm going to let you work out the formula for yourself. The key >observations are (a) if the difference between the number of 0's >and 1's is even the final xor is 0, otherwise it is odd, (b) in >bit position k (starting the position number with 0) there are >alternating sequences of 2^k 0's and 2^k 1's in the sequence of >integers, (c) in consequence of (b) we only need to look at N >modulo 2^(k+1), and (d) we only need to know whether N modulo >2^(k+1) is odd or even. Mea culpa. The above is wrong. The key observation is that if we xor a mixed sequence of 0's and 1's the result is 0 if the number of 1's is even and 1 if it is odd. Bit 0 of the xor is the complement of bit 0. For bit k of the xor set m = N mod 2^(k+1). If m < 2^k bit k of the xor is 0. Otherwise it is the complement of bit 0 of m. I hope I haven't screwed this up yet again. :-) 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.   0 cri (1432) 1/12/2009 12:16:00 PM On Jan 12, 4:16=A0am, c...@tiac.net (Richard Harter) wrote: > On Mon, 12 Jan 2009 05:00:11 GMT, c...@tiac.net (Richard Harter) > wrote: > > >On Sat, 10 Jan 2009 20:12:43 GMT, Juha Nieminen > ><nos...@thanks.invalid> wrote: > > >>Richard Harter wrote: > >>> You can also precompute what the result of xor'ing all of the > >>> numbers from 1 to N would be > > >> =A0Out of curiosity: Is there any faster way of doing that other than > >>making a loop from 1 to N and xorring the loop counter? > > >> =A0I was thinking something along the lines of: If N modulo 4 is 1 or = 2, > >>you know the least-significant bit of the xor will be 1, else it will b= e > >>0. Could similar rules be developed for all the other bits as well? > > >I'm going to let you work out the formula for yourself. =A0The key > >observations are (a) if the difference between the number of 0's > >and 1's is even the final xor is 0, otherwise it is odd, (b) in > >bit position k (starting the position number with 0) there are > >alternating sequences of 2^k 0's and 2^k 1's in the sequence of > >integers, (c) in consequence of (b) we only need to look at N > >modulo 2^(k+1), and (d) we only need to know whether N modulo > >2^(k+1) is odd or even. =A0 > > Mea culpa. =A0The above is wrong. =A0The key observation is that if > we xor a mixed sequence of 0's and 1's the result is 0 if the > number of 1's is even and 1 if it is odd. =A0Bit =A00 of the xor is > the complement of bit 0. =A0For bit k of the xor set m =3D N mod > 2^(k+1). =A0If m < 2^k bit k of the xor is 0. =A0Otherwise it is the > complement of bit 0 of m. > > I hope I haven't screwed this up yet again. =A0:-) Well ... I don't know about these hints. Remember that he was originally looking at N (mod 4) which is not a bad place to start in figuring out the xor-sum formula. If you don't have the math insight, it takes very little effort to figure it out by brute force: Just print out the first 100 results in 4 columns and 50% of the pattern will be blatantly obvious, while each of the remaining 25% will probably be clear enough. Then its a very simple matter of proving it. -- Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/   0 websnarf (1153) 1/13/2009 2:22:44 AM On Mon, 12 Jan 2009 18:22:44 -0800 (PST), Paul Hsieh <websnarf@gmail.com> wrote: >On Jan 12, 4:16=A0am, c...@tiac.net (Richard Harter) wrote: >> On Mon, 12 Jan 2009 05:00:11 GMT, c...@tiac.net (Richard Harter) >> wrote: >> >> >On Sat, 10 Jan 2009 20:12:43 GMT, Juha Nieminen >> ><nos...@thanks.invalid> wrote: >> >> >>Richard Harter wrote: >> >>> You can also precompute what the result of xor'ing all of the >> >>> numbers from 1 to N would be >> >> >> =A0Out of curiosity: Is there any faster way of doing that other than >> >>making a loop from 1 to N and xorring the loop counter? >> >> >> =A0I was thinking something along the lines of: If N modulo 4 is 1 or = >2, >> >>you know the least-significant bit of the xor will be 1, else it will b= >e >> >>0. Could similar rules be developed for all the other bits as well? >> >> >I'm going to let you work out the formula for yourself. =A0The key >> >observations are (a) if the difference between the number of 0's >> >and 1's is even the final xor is 0, otherwise it is odd, (b) in >> >bit position k (starting the position number with 0) there are >> >alternating sequences of 2^k 0's and 2^k 1's in the sequence of >> >integers, (c) in consequence of (b) we only need to look at N >> >modulo 2^(k+1), and (d) we only need to know whether N modulo >> >2^(k+1) is odd or even. =A0 >> >> Mea culpa. =A0The above is wrong. =A0The key observation is that if >> we xor a mixed sequence of 0's and 1's the result is 0 if the >> number of 1's is even and 1 if it is odd. =A0Bit =A00 of the xor is >> the complement of bit 0. =A0For bit k of the xor set m =3D N mod >> 2^(k+1). =A0If m < 2^k bit k of the xor is 0. =A0Otherwise it is the >> complement of bit 0 of m. >> >> I hope I haven't screwed this up yet again. =A0:-) > >Well ... I don't know about these hints. Remember that he was >originally looking at N (mod 4) which is not a bad place to start in >figuring out the xor-sum formula. If you don't have the math insight, >it takes very little effort to figure it out by brute force: Just >print out the first 100 results in 4 columns and 50% of the pattern >will be blatantly obvious, while each of the remaining 25% will >probably be clear enough. Then its a very simple matter of proving >it. I worked out an entirely different approach; I wasn't familiar with the formula you are talking about, which is a much simpler approach. 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.   0 cri (1432) 1/16/2009 6:35:58 AM On Jan 10, 3:59=A0pm, Paul Hsieh <websn...@gmail.com> wrote: > On Jan 10, 10:55=A0am, Tagore <c.lang.mys...@gmail.com> wrote: > > > * suppose you have a set of unsorted numbers from 1 to N (a big > > number, say 1 million). One number is missing, how to find that > > missing number most efficiently? > > > Adding the number then subtract N(N+1)/2 may not be possible since the > > number could be too big to store. > > You only require that you calculate the sum modulo K, where K > N. > I.e., if the number is too big, go ahead and let it wrap around. > There are complicated ways of computing N(N+1)/2 doing this through > direct calculation, but why bother: > > =A0 =A0 numSum =3D 0; > =A0 =A0 inputSum =3D 0; > =A0 =A0 for (i=3D0; i < N-1; i++) { > =A0 =A0 =A0 =A0 numSum +=3D i; > =A0 =A0 =A0 =A0 inputSum +=3D array[i]; > =A0 =A0 } > =A0 =A0 return (numSum + N-1) - inputSum; It's not even necessary to keep two separate sums: Sum =3D N-1; for (i=3D0; i < N-1; i++) Sum +=3D i - array[i]; return Sum;   0 robertwessel2 (1674) 1/16/2009 6:53:06 AM "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> writes: > On Jan 10, 3:59�pm, Paul Hsieh <websn...@gmail.com> wrote: >> On Jan 10, 10:55�am, Tagore <c.lang.mys...@gmail.com> wrote: >> >> > * suppose you have a set of unsorted numbers from 1 to N (a big >> > number, say 1 million). One number is missing, how to find that >> > missing number most efficiently? >> >> > Adding the number then subtract N(N+1)/2 may not be possible since the >> > number could be too big to store. >> >> You only require that you calculate the sum modulo K, where K > N. >> I.e., if the number is too big, go ahead and let it wrap around. >> There are complicated ways of computing N(N+1)/2 doing this through >> direct calculation, but why bother: Computing the XOR of all the numbers works too. It takes less memory since you only need the number of bits of the biggest number, N. (defun test (n) (let ((missing (random n))) (loop :for i :from 1 :to n :for xor = (if (= i missing) 0 i) :then (if (= i missing) xor (logxor xor i)) :finally (setf xor (logxor n xor)) (return (values xor missing (= xor missing)))))) (loop :repeat 10 :do (print (multiple-value-list (test 1000000)))) (340555 340555 T) (228983 228983 T) (854712 854712 T) (662113 662113 T) (371568 371568 T) (907540 907540 T) (889816 889816 T) (670949 670949 T) (109844 109844 T) (544193 544193 T) (But I don't understand why we need to xor N again to get the result...) -- __Pascal Bourguignon__   0 pjb (7869) 1/16/2009 9:46:40 AM In article <2d6e8332-d116-4d55-a6e2-ca0e204a63c5 @n33g2000pri.googlegroups.com>, c.lang.myself@gmail.com says... > * suppose you have a set of unsorted numbers from 1 to N (a big > number, say 1 million). One number is missing, how to find that > missing number most efficiently? > > Adding the number then subtract N(N+1)/2 may not be possible since the > number could be too big to store. Well, a little modulo arithmetic should solve this particular homework problem. - Gerry Quinn   0 gerryq2 (435) 1/23/2009 4:18:09 AM  Reply: Similar Artilces: Number sequences, programming, preparing for Programming Competition Hello, As programmers are very smart and mostly well educated with a strong mathematical background, I ask this question here as well as sci.math and sci.math.num-analysis by posting a this message to each of those groups. I am preparing for a student programming competition and from the previous year experience I know that there are 2 'simply programming' problems and a single one which involves strong mathematics. I am very experienced programmer (6years +) so those 2 'simply programming' are not problems for me. But to win the competition I have ... Program or be Programmed http://www.rushkoff.com/program-or-be-programmed/ The debate over whether the Net is good or bad for us fills the airwaves and the blogosphere. But for all the heat of claim and counter-claim, the argument is essentially beside the point: it's here; it's everywhere. The real question is, do we direct technology, or do we let ourselves be directed by it and those who have mastered it? ?Choose the former,? writes Rushkoff, ?and you gain access to the control panel of civilization. Choose the latter, and it could be the last real choice you get to make.? ... write a C++ program to print number of zeros of a series of 10 numbers entered by the user. write a C++ program to print number of zeros of a series of 10 numbers entered by the user. "???? ???" <md.rg8910@gmail.com> wrote in message news:ef767427-e67e-4a47-a047-a2fc3208dbd4@googlegroups.com... > write a C++ program to print number of zeros of a series of 10 numbers > entered by the user. As I understand it, this is your current status: int main() { // I need something here } That's too vague to expect any help. Make _some_ attempt and post it, even if you don't actually like what you post. On 3/30/2015 8:56 AM, مح... Need to replace missing values with zeros in a varying number of rows and varying number of columns People, I am working in PC SAS v8.1 I have a program that finds the number of times a varying number of people get a document to different levels of completeness. The program displays this information from the beginning of the current month to the current day. Using a separate column for each day. So as the month continues the number of days(columns) increases. If person A does not get a document to level 2 completeness on a certain day the field currently is blank. The user would like the report to display zeros instead of blanks. I create the report in SAS and then export the final repo... 2005-Jan-12-to-2004-Nov-01 new programs, and instructions how to authorise, register, including the authorization, registration, and installation serial numbers for 20,000 plus programs 2005-Jan-12-to-2004-Nov-01 new programs, and instructions how to authorise, register, including the authorization, registration, and installation serial numbers for 20,000 plus programs 2005/01/12 Cinema.Craft.Encoder.SP.v2.70.01.05 2005/01/12 Magic.Bullet.Editor.v.1.01.for.Avid.Xpress.Pro 2005/01/12 Magic.Bullet.Editor.v.1.01.for.Premiere.Pro 2005/01/12 Magic.Bullet.Editor.v.1.01.for.Sony.Vegas 2005/01/12 Evasion3D.X-Dof.v2.1.for.Mental.Ray 2005/01/12 Texture Shaker V1.0 Dec 22 2005/01/12 Collage.Builder.Power.Console.v1.0.for.Photoshop 2005/01/12 EGS.FeatureCAM.2005.V11.4.0.19... 2005-Jan-12-to-2004-Nov-01 new programs, and instructions how to authorise, register, including the authorization, registration, and installation serial numbers for 20,000 plus programs 2005-Jan-12-to-2004-Nov-01 new programs, and instructions how to authorise, register, including the authorization, registration, and installation serial numbers for 20,000 plus programs 2005/01/12 Cinema.Craft.Encoder.SP.v2.70.01.05 2005/01/12 Magic.Bullet.Editor.v.1.01.for.Avid.Xpress.Pro 2005/01/12 Magic.Bullet.Editor.v.1.01.for.Premiere.Pro 2005/01/12 Magic.Bullet.Editor.v.1.01.for.Sony.Vegas 2005/01/12 Evasion3D.X-Dof.v2.1.for.Mental.Ray 2005/01/12 Texture Shaker V1.0 Dec 22 2005/01/12 Collage.Builder.Power.Console.v1.0.for.Photoshop 2005/01/12 EGS.FeatureCAM.2005.V11.4.0.19 2005/01/12 EGS.FeatureCAM.2005.V11.4.0.19.CATIA.5.Plugin 2005/01/12 EGS.FeatureCAM.2005.V11.4.0.19.SOLID.EDGE.Plugin 2005/01/12 EGS.FeatureCAM.2005.V11.4.0.19.SOLID.Plugin 2005/01/12 SCIA.ESA.PT.V5.0.379 2005/01/12 SUM3D v7.1 2005/01/12 Aldec.Riviera.v2004.12.1684 2005/01/12 Bitplane.Imaris.v4.1.3 2005/01/12 Unilet PRO v6.0.1 Multilingual 2005/01/12 Avid.Xpress.Pro.HD.v5.0 1CD 2005/01/12 Magic.Bullet.Editors.v1.01.WinMAC 1CD 2005/01/12 Pandromeda.MojoWorld.v3 Professional 3CD 2005/01/12 Digidesign.Protools.LE.v6.7.WinXP 1CD 2005/01/12 MSC Documentation 2005 1CD 2005/01/12 Total.Training.Adobe.Audition.1.5.Project.Files 1CD 2005/01/08 Avid.Xpress.Pro.HD.v5.0 2005/01/08 Sony.Vegas.v5.0d 2005/01/08 Act3d.Quest3D.v2.5a.Enterprise.Edition 2005/01/08 Deliverance.Software.Geoscape3d.v1.2.0.16 2005/01/08 CD.adapco.STAR-CD.v3.24.LiNUX 2005/01/08 Layerman.v4.1g.for.AutoCad 2005/01/07 Kajima Reals 3D v2.04... Numbering missing visits Dear all, How do I count the consecutive missing visitid (M) per PT and get the expected counts below? pt visdat visitid count (expected) 1 12JAN2008 1 . 1 20JAN2008 2 . 1 03FEB2008 M 1 1 15FEB2008 M 2 2 03JAN2008 1 . 2 27JAN2008 M 1 2 12FEB2008 2 . 2 25FEB2008 3 . 2 12MAR2008 M 1 2 28MAR2008 M 2 2 19APR2008 M 3 Many thanks & Kind regards, Franz On Oct 28, 12:16=A0pm, MichelleZ <michelle_zunnur...@hotmail.com> wrote: > On Oct 27, 7:11=A0am, franz_cl2...@yahoo.fr (Franz) wrote: > > > > > > > Dear all, > > > How do I count the consecutive missing visitid (M) per PT and get the e= xpected counts below? > > > pt =A0 =A0 =A0visdat =A0 =A0 =A0 =A0 =A0visitid =A0 =A0 =A0 =A0 =A0 =A0= =A0 =A0count (expected) > > 1 =A0 =A0 =A0 12JAN2008 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 1 =A0 =A0 = =A0 =A0 =A0 . > > 1 =A0 =A0 =A0 20JAN2008 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 2 =A0 =A0 = =A0 =A0 =A0 . > > 1 =A0 =A0 =A0 03FEB2008 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 M =A0 =A0 = =A0 =A0 =A0 1 > > 1 =A0 =A0 =A0 15FEB2008 =A0 =A0 ... find the missing number...... Hello everybody! I have a series of numbers like the following 703001 703002 703004 703005 703008 703010 I want to get the missing numbers. Here they are.. 703003 703006 703007 703009 I wrote the following code to get the difference of the numbers but failed to get the missing numbers... awk '{ ar[NR]=$0}END{ for (i=1; i<=NR; i++){ printf "%6d - %6d = %2d\n",ar[i+1],ar[i],ar[i +1]-ar[i]}}' input how to get the missing numbers. Please gimmi an idea. Thank you. nag wrote: > Hello everybody! > > I have a series of numbers like the following > > 703001 > 703002 > 703004 > 703005 > 703008 > 703010 > > I want to get the missing numbers. Here they are.. > > 703003 > 703006 > 703007 > 703009 > > I wrote the following code to get the difference of the numbers but > failed to get the missing numbers... > > awk '{ ar[NR]=$0}END{ > for (i=1; i<=NR; i++){ printf "%6d - %6d = %2d\n",ar[i+1],ar[i],ar[i > +1]-ar[i]}}' input > > how to get the missing numbers. Please gimmi an idea. Thank you. Assuming there are no missing numbers before the first entry and after the last... awk '($0 - p) > 1 && NR>1{for(i=p+1;i<$0;i++)print i} {p =$0}' On 3/12/2010 9:36 AM, nag wrote: > Hello everybody! > > I have a series of numbers like the following > > 703001 > 703002 > 703004 > 703005 > 703008 > 703010 &...

The number of programming in a computer
Dear all, &nbsp; I have a question about the number of labview program in a computer which could be run at the same time. Please let me know how to run two or more different programs at the same time. &nbsp; Thank you in advance. Hi: I'm not sure what are you talking about. Do you mean how many VI's can you start on LabVIEW at the same time? Or you mean how many applications compiled can run on the same computer? In both cases, the limit is impossed by your PCs available resources. If you want to run two or more VIs in LabVIEW just make visible the front panel of all of the...

Missing Program group
Guys and Girls I have a server that was running SQL Server 2000 (on Windows 2000 server). In preperation for an upgrade from an old SQL Server 6.5 system. I un-installed 2000. I edited the registry to remove all references to SQL Server and deleted all files. I have rebooted the server. I have run an install of 6.5. It seems to have worked all right except there is no program groups on my start menu. Any ideas what might have happened? Regards Matt <john.bandettini@rbs.co.uk> wrote in message news:1117786641.708591.159230@g49g2000cwa.googlegroups.com... > Guys and Girls > > I have a server that was running SQL Server 2000 (on Windows 2000 > server). > In preperation for an upgrade from an old SQL Server 6.5 system. I > un-installed 2000. I edited the registry to remove all references to > SQL Server and deleted all files. I have rebooted the server. > > I have run an install of 6.5. It seems to have worked all right except > there is no program groups on my start menu. Any ideas what might have > happened? > > Regards > > Matt > No idea, but presumably you can easily create your own group and add shortcuts to the various executables? You could even copy the group from another machine, if you have one available. Simon ...

apocalyptic number program
Write a program which tests the Apocalyptic number. An Apocalyptic number is: "A number of the form 2^n that contains the digits 666 (i.e., the beast number) is called an apocalyptic number.The first few such powers are 157, 192, 218, 220, ..." The list goes on.... Program should only take power(n) as input (which is 2^n ) for any given values as said above and the output should whether this power will form apocalyptic number or not. So here my data type should be capable enough to hold for any (dynamic in nature)powered number which may run into 50's or ...

missing table numbers

apocalyptic number program
Write a program which tests the Apocalyptic number. An Apocalyptic number is: "A number of the form 2^n that contains the digits 666 (i.e., the beast number) is called an apocalyptic number.The first few such powers are 157, 192, 218, 220, ..." The list goes on.... Program should only take power(n) as input (which is 2^n ) for any given values as said above and the output should whether this power will form apocalyptic number or not. So here my data type should be capable enough to hold for any (dynamic in nature)powered number which may run into 50's or 100' digits of generated out of 2^n. FOr example like 2^499 is 'apocalyptic': 163669530394807093500659484841379957610832102302153239474164568404806689820= =AD=AD 233727744163504616295207857544334206378003550460862827294269652666426379468= =AD=AD 8 P.S: you need to print that value from ur data structure used for storing it not the direct output of pow(2,n) !!! For any clarifications write back :) rajshekhar3@gmail.com writes: > Write a program which tests the Apocalyptic number. > An Apocalyptic number is: > "A number of the form 2^n that contains the digits 666 (i.e., the > beast number) is called an apocalyptic number.The first few such > powers are 157, 192, 218, 220, ..." > The list goes on.... > > > Program should only take power(n) as input (which is 2^n ) for any > given values as said above This is...

equation number, table number, figure number linked to the same paragraph number
I have a paragraph number, example A-XXX Then I want to have equations like: .... Eq A-1 .... Eq A-2 ... liked to this paragraph And also ... fig A-1 .... fig A-2 ...linked only to this paragraph .... At the end. I want to have... A-XXX .... Eq A-1 .... fig A-1 .... fig A-2 .... Eq A-2 .... Eq A-3 .... fig A-3 B-XXX .... Eq B-1 .... fig B-1 .... Eq A-2 .... Eq A-3 .... fig B-2 Thanks for ideas On Sat, 17 Nov 2007 23:22:15 +0100, value <####@wanadoo.fr> wrote: > I have a paragraph number, example > > A-XXX > > T...

A number of packages are being missed by rubygems
I'm trying to download packages via rubygems, but only a subset of the packages that are available on the rubygems site are showing up when I do queries. The list at the bottom of this message is what I get when I issue the "gem query --remote" command. However, if I go directly to the "http://gems.rubyforge.org/gems/" site, there are a number of other packages listed which don't show up when I do the query. I also see all those other packages when I look in the yaml index at "http://gems.rubyforge.org/yaml". Does anyone know why my version of rubygems...

lineno misses line numbers
Hello, I am writing a paper for an Elsevier journal using their supplied documentclass elsart.cls. The help for this document class recommends the lineno package for numbering lines for review. The problem is that for some pages, there is no line numbering in a part of the page. Anyone aware of this problem and a possible solution. Thanks in advance. Sincerely, Ashish ...

Function missing for complex numbers
I am translating complex number codes from fortran and C++ into the C99 notation. Since this notation is not used in any significant package (that I know of), translating other languages codes is unavoidable. What is missing (besides several other stuff) is a function that takes two floating point numbers and returns a complex. C++ provides the constructor, what would NICE to have in C99. Fortran has CMPLX(real,imag). long double _Complex Complexl(long double,long double); double _Complex Complex(double,double); float _Complex Complexf(float,float); This would make easier to translate codes from C++ and Fortran into C. As it is now, the function call must be replaced C=complex(A,B) --> C = A + (I*(b)), what is quite different and contributes to the difficulty of translating those codes. Thanks for your attention -- jacob navia jacob at jacob point remcomp point fr logiciels/informatique http://www.cs.virginia.edu/~lcc-win32 jacob navia <jacob@nospam.org> writes: > I am translating complex number codes from fortran and C++ into the C99 > notation. > > Since this notation is not used in any significant package (that I > know of), translating other languages codes is unavoidable. > > What is missing (besides several other stuff) is a function that takes > two floating point numbers and returns a complex. C++ provides the > constructor, what would NICE to have in C99. Fortran has > CMPLX(re...

Field missing from a program dump
I just added some code to a pgm and now I'm getting an array index error. No surprise there. However, the dump only has 54 pages when it use to be 200+ pages and lots of fields and data structures are missing from the dump. I can't seem to see any pattern to which items are missing from the dump. Some field which are full of data do not even show as being in the program. For instance, the following data structure has data (I'm viewing it a debug session at the line before the failed line) 0777.00 D DETPRT DS 150 OCCURS(500) Yet in the dump all that shows is this. DETPRT CHAR(1) NOT ADDRESSABLE I remember having this problem a decade ago but it hasn't come up since and I don't remember what cured the problem of them missing fields (other than fixing the program so it doesn't fail) [smile] any ideas would be appreciated. Steve On Aug 27, 8:31 am, "NHRunner" <seniorrun...@aol.com> wrote: > I just added some code to a pgm and now I'm getting an array index error. No > surprise there. > > However, the dump only has 54 pages when it use to be 200+ pages and lots of > fields and data structures are missing from the dump. > > I can't seem to see any pattern to which items are missing from the dump. > > Some field which are full of data do not even show as being in the program. > For instance, the following data structure has data (I'm view...

Rankings & missing out numbers
It may be the nasty head cold, but I've got a problem I can't seem to bend my brain around: We've got a list of students and their average exam marks (calculated in another part of the database on the fly). What we need to do is rank them, and that's the bit I'm having trouble with. Even though we're calculating the average to two decimal places, sometimes two or more students will have the same average. e.g. Tom Davis 82.35 Alex Taylor 80.21 Jane Doe 80.21 Sue Brown 80.21 Sally Smith 70.82 What we'd like is for Tom to be '1', Alex, Jane and Sue to be '2' and Sally to be '5'. Is this something I can do with some VBA code or can Access maybe do it on it's own? Any pointers in the right direction would be most helpful and appreciated! -Jen (using Access 2003; to reply by email, remove the spork from my address) See: Ranking or numbering records at: http://allenbrowne.com/ranking.html#query I think the 'Ranking in a Query' example is the one you are looking for. -- Allen Browne - Microsoft MVP. Perth, Western Australia Tips for Access users - http://allenbrowne.com/tips.html Reply to group, rather than allenbrowne at mvps dot org. "Jen P." <jp337spork@cam.ac.uk> wrote in message news:geuk16$7j6$1@gemini.csx.cam.ac.uk... > It may be the nasty head cold, but I've got a problem I can't seem to bend > my brain around: We've got a list of students and t...

count the number of missing values
Hello,. How can I get the number of missing values in a dataset. I mean, suppose there are dataset test with variables x1,x2, and x3. I would like to know how many missing values are there. Best regards, Hi, for individual variables you can use the function missing() e.g: if Missing(x1) = 1 then miss_cnt_x1 = miss_cnt_x1 + 1; or for combined missing you can use: if Missing(x1) and Missing(x2) and Missing(x3) then all_miss_cnt = all_miss_cnt + 1; A quick and dirty alternative is do a proc freq with missing option : e.g: proc freq data= test; tables x1 x2 x3 /missing; run; this will tell y...

missing arg for complex number
Hi. As I can see, the arg function for complex numbers -- for polar representation: z = abs(x) exp(arg(z)) -- is missing! Why? Thanks and regards Manlio Perillo Manlio Perillo <NOmanlio_perilloSPAM@libero.it> wrote in message news:<he01d0h4je91d0g37d6do6vrmvmn2a914o@4ax.com>... > Hi. > As I can see, the arg function for complex numbers > -- for polar representation: z = abs(x) exp(arg(z)) -- > is missing! > Why? Probably just an oversight. But it's easy to implement. def phase(z): return math.atan2(z.imag, z.real) ...

mpich: missing program name
Hi, whenever I want to run a program I have to specify a full pathname. tyr hello1 102 mpirun -np 3 hello1_mpi Missing: program name Program hello1_mpi either does not exist, is not executable, or is an erroneous argument to mpirun. tyr hello1 103 which hello1_mpi /home/fd1026/SunOS/sparc/bin/hello1_mpi tyr hello1 104 mpirun -np 3 /home/fd1026/SunOS/sparc/bin/hello1_mpi Now 2 slave tasks are sending greetings. Greetings from task 1: .... Does MPICH always require full pathnames or is something wrong with my installation (missing environment variable; programs must be stored in a special ...

Re: Numbering missing visits
data visit; input pt:$1 visdat:date. visitid :$1.; format visdat date.; cards; 1 12JAN2008 1 . 1 20JAN2008 2 . 1 03FEB2008 M 1 1 15FEB2008 M 2 2 03JAN2008 1 . 2 27JAN2008 M 1 2 12FEB2008 2 . 2 25FEB2008 3 . 2 12MAR2008 M 1 2 28MAR2008 M 2 2 19APR2008 M 3 ;;;; run; proc sort data=visit; by pt visdat; run; data visit; call missing(count); do until(last.visitID); set work.visit; by pt visitID notsorted; if visitID eq 'M' then count + 1; output; end; run; proc print; run; On 10/27/08, Franz <franz_cl2003@yahoo.fr> wrote: > Dear all, > > How do I count the consecutive missing visitid (M) per PT and get the expected counts below? > > pt visdat visitid count (expected) > 1 12JAN2008 1 . > 1 20JAN2008 2 . > 1 03FEB2008 M 1 > 1 15FEB2008 M 2 > 2 03JAN2008 1 . > 2 27JAN2008 M 1 > 2 12FEB2008 2 . > 2 25FEB2008 3 . > 2 12MAR2008 M 1 > 2 28MAR2008 M 2 > 2 19APR2008 ...

Looking for number crunching program
Hello all, I am looking for programs to do memory and CPU load test on my systems. Does anybody have one? Thanks, Tuan Tuan Dang wrote: > Hello all, > > I am looking for programs to do memory and CPU load test on my systems. > Does anybody have one? > > Thanks, > Tuan > do you know about the sun validation and test suite? (http://www.sun.com/oem/products/vts/) Tom ...

Web resources about - MISSING NUMBER - comp.programming

Missing in Action (video game) - Wikipedia, the free encyclopedia
M.I.A.: Missing in Action is platform arcade game released by Konami in 1989. The game is a spiritual successor to Green Beret (also known as ...

Facebook Alerts Users To How Many Stories They’re Missing On News Feed
Facebook wants users to make sure they’re not missing anything on News Feed . Several users on the redesigned News Feed have started seeing notifications ...

Chronik-Fotos - Missing Kyron Horman - Facebook
A message from Kyron's Momma, Desiree. As I sit here in the silence of our home, my mind wanders to Kyron. I miss all of the giggles that have... ...

Facebook held a press conference today to announce the launch of 53 AMBER Alert Pages that will dispatch bulletins about missing children via ...

Search under way for health worker Gayle Woodford missing in APY Lands - AdelaideNow Search Search
POLICE hold serious concerns for a nurse who was abducted from her remote home in South Australia’s Far North, with her disappearance declared ...

Missing nurse declared major crime
POLICE hold serious concerns for a nurse who was abducted from her remote home in South Australia’s Far North, with her disappearance declared ...

'Precariat' generation missing out on Australian lifestyle
The gap between generations is growing with young people behind in material wealth and mental wellbeing, a new book reveals.

Body found in search for missing SA nurse Gayle Woodford
The body of a woman believed to be that of missing health worker Gayle Woodford has been found in South Australia.

Police find body believed to be that of missing South Australian nurse Gayle Woodford
Police locate a body believed to be that of missing outback SA nurse Gayle Woodford.

Family in central Ohio prays missing couple is found safe after Brussels attacks
Lesa Stone's niece and her husband have been missing since the attacks this week.

Resources last updated: 3/26/2016 4:52:01 PM