Prev: security problems in bash script
Next: Next Generation Test Management System
From: pete on 3 Jul 2008 23:54
srk 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.

There are other ways to do it but,
your question is an xor checksum exercise.

xor all the numbers from 1 to n,
and xor that result with the xor of all the numbers in the array.
The result will be the missing value.

Suppose n is 4
and there's only 3 elements in the array

1 xor 2 xor 3 xor 4 is (4).

Take that result, (4),
and xor (4) with the xor of all the elements in the array.
The result will be the missing value.

If the array is {4,2,3}, the missing value is 1.
(4 xor 2 xor 3) xor (4) is 1

If the array is {4,3,1}, the missing value is 2.
(4 xor 3 xor 1) xor (4) is 2

If the array is {2,1,4}, the missing value is 3.
(2 xor 1 xor 4) xor (4) is 3

If the array is {3,2,1}, the missing value is 4.
(3 xor 2 xor 1) xor (4) is 4


--
pete
From: Ben Pfaff on 4 Jul 2008 01:15
pete <pfiland(a)mindspring.com> writes:

> srk 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.
>
> There are other ways to do it but,
> your question is an xor checksum exercise.

I think that it takes a programmer to regard this as a question
most naturally answered with xor. Anyone else would use
subtraction: sum the numbers in the array and subtract from
n*(n+1)/2.
--
Ben Pfaff
http://benpfaff.org
From: pete on 4 Jul 2008 10:57
Ben Pfaff wrote:
> pete <pfiland(a)mindspring.com> writes:
>
>> srk 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.
>> There are other ways to do it but,
>> your question is an xor checksum exercise.
>
> I think that it takes a programmer to regard this as a question
> most naturally answered with xor.

What a nice thing to say, especially in the context of this newsgroup.

Thank you.

> Anyone else would use
> subtraction: sum the numbers in the array and subtract from
> n*(n+1)/2.


--
pete
From: Ben Pfaff on 4 Jul 2008 17:04
pete <pfiland(a)mindspring.com> writes:

> Ben Pfaff wrote:
>> pete <pfiland(a)mindspring.com> writes:
>>
>>> srk 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.
>>> There are other ways to do it but,
>>> your question is an xor checksum exercise.
>>
>> I think that it takes a programmer to regard this as a question
>> most naturally answered with xor.
>
> What a nice thing to say, especially in the context of this newsgroup.
>
> Thank you.

It is always hard to read emotions over Usenet, and so I can't
tell if you are sarcastic. If you are, then I apologize; I had
no intention to cause offense.
--
"In this world that Hugh Heffner had made,
he alone seemed forever bunnyless."
--John D. MacDonald
From: pete on 4 Jul 2008 19:38
Ben Pfaff wrote:
> pete <pfiland(a)mindspring.com> writes:
>
>> Ben Pfaff wrote:
>>> pete <pfiland(a)mindspring.com> writes:
>>>
>>>> srk 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.
>>>> There are other ways to do it but,
>>>> your question is an xor checksum exercise.
>>> I think that it takes a programmer to regard this as a question
>>> most naturally answered with xor.
>> What a nice thing to say, especially in the context of this newsgroup.
>>
>> Thank you.
>
> It is always hard to read emotions over Usenet, and so I can't
> tell if you are sarcastic. If you are, then I apologize; I had
> no intention to cause offense.

You called me a "programmer" on comp.programming.

Your comment certainly could be taken as a compliment,
especially in the context of this newsgroup,
so that's what I decided to do.

It occurred to me that I might have written what you wrote,
and not intended it as a compliment,
but there's no way that I could have intended it as an insult,
except maybe to everybody else who posted an non xor solution.

--
pete
 | 
Pages: 1
Prev: security problems in bash script
Next: Next Generation Test Management System