Re: find a number
- From: Mark P <usenet@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Sat, 25 Mar 2006 01:20:35 GMT
"Arthur J. O'Dwyer" wrote:On Fri, 24 Mar 2006, Mark P wrote:Sc0rpi0 wrote:Does it depend on the array elements' being the numbers 1 throughmurali@pune wrote:Those algorithms work nicely.I have an array of 1001 integers. The integers are in randomhint 1: Sum of all not repeated ints is 1+2+...+1000
order, but I know each of the integers is between 1 and 1000
(inclusive). In addition, each number appears only once in the
array, except for one number, which occurs twice.
or hint 2: XOR of all not repeated ints is 1^2^...^1000.
There's also a cute algorithm for this problem which runs in
linear time, uses constant space, and performs no arithmetic
computations on the array elements.
Any takers? :)
N? If so, does it have any resemblance to the classic "find the
loop in the linked list" interview answer? :)
I can't think of any linear-time, constant-space solution if we
don't restrict the element values to the integers 1 through N,
or some set with an easy bijection onto those integers.
There is a great difference between arithmetic on the elements, and
arithmetic with the elements.
Perhaps you can explain what this difference is?
s = 0; i = 0;
s -= i; s += a[i++];
} while (i <= 1001);
printf("duplicate is %d\n", s);
requires extending the array to a zeroth element, which is zero.
Not quite right, even allowing for the unusual convention that the original array is indexed starting from 1. Hint: what's the sign of the value that gets printed?
The code above avoids that, so that the acquisition of a[i] can be
replaced by a 'getnext()' operation, emphasizing that no arithmetic
is 'done on' the element.
Which code avoids that?
Semantic debates asides, by my original statement "performs no arithmetic computations on the array elements," I really mean that no arithmetic is done period.
- Re: find a number
- From: CBFalconer
- Re: find a number
- Prev by Date: Re: Checking for Modification to a Set of Files
- Next by Date: Robotic Group
- Previous by thread: Re: find a number
- Next by thread: Re: find a number