Re: searching for missing element in an array
- From: pete <pfiland@xxxxxxxxxxxxxx>
- Date: Thu, 03 Jul 2008 22:54:34 -0500
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
.
- Follow-Ups:
- Re: searching for missing element in an array
- From: Ben Pfaff
- Re: searching for missing element in an array
- Prev by Date: security problems in bash script
- Next by Date: Next Generation Test Management System
- Previous by thread: security problems in bash script
- Next by thread: Re: searching for missing element in an array
- Index(es):
Relevant Pages
|
