Re: find a number

CBFalconer wrote:
"Arthur J. O'Dwyer" wrote:
On Fri, 24 Mar 2006, Mark P wrote:
Sc0rpi0 wrote:
murali@pune wrote:
I have an array of 1001 integers. The integers are in random
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.
hint 1: Sum of all not repeated ints is 1+2+...+1000
or hint 2: XOR of all not repeated ints is 1^2^...^1000.
Those algorithms work nicely.

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? :)
Does it depend on the array elements' being the numbers 1 through
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;
do {
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.
.

Relevant Pages

  • Re: tictactoe
    ... >> a new array based on an existing array where the new one has x's where ... Here's your original array: ... You want the second array to have the same number of elements as the ... The loop examines each element of the original array one at a time, ...
    (comp.lang.java.help)
  • Re: Ranking Without Sorting
    ... >some point you want to use an ordering of the original array... ... >in the original array (an array of pointers, reference, indices, whatever ... >works nicest in the target language) and sort that. ... Since a ranking can be used to sort an array in time O, ...
    (comp.programming)
  • Re: Mann-Kendall test statistic
    ... >> ie. it is the sum of the signs of all pairwise differences. ... filled slots to an item's left and right is the number of +ve and -ve ... the size of the original array. ...
    (sci.stat.math)
  • Re: safe to delete elements of array in foreach
    ... I make it a habit not to delete entries in a foreach() loop. ... build an array of keys I want to delete, and after the loop ends, delete ... I don't know whether an operation like this is guaranteed to work in PHP ... So unsetting a value in the original array should not affect the copy ...
    (comp.lang.php)
  • Re: random array elements and speed
    ... # need int here since we are checking for dups and floats won't work ... case I were to need more elements than those in the returned array. ... that could theoretiocally never terminate. ... the original array, but small's a relative term and the expected speed ...
    (comp.lang.perl.misc)