Finding Repeated and Missing Numbers

[Harsha Srinath]

Athough this might not be directly relayed to C syntax, I thought some
of you may find this an interesting problem :-

1.One number, in an array integers from 1 to 1,000,000 is present
twice. How can you determine which one? Can you think of a way to do
it using little extra memory?

2. How would you find the only missing element in that array? Can you
think of a way to do it while iterating through the array only once. Is
overflow a problem in the solution? Why not?

For both the problems, the solution I can think of is to sort
the elements and then compare consecutive elements (in O(nlogn) time).
Summing the numbers didn't seem of much use. Creating another such
array and then using the elements as indices may not be that neat of an
approach from a memory perspective, I felt.

Any other ways, folks?

Thanks,
Harsha

[Richard Harter]

Re: Finding Repeated and Missing Numbers

On 26 Jun 2005 22:51:10 -0700, "Harsha Srinath" <harshayes@gmai l.com>
wrote:
[color=blue]
>Athough this might not be directly relayed to C syntax, I thought some
>of you may find this an interesting problem :-
>
>1.One number, in an array integers from 1 to 1,000,000 is present
>twice. How can you determine which one? Can you think of a way to do
>it using little extra memory?
>
>2. How would you find the only missing element in that array? Can you
>think of a way to do it while iterating through the array only once. Is
>overflow a problem in the solution? Why not?
>
>For both the problems, the solution I can think of is to sort
>the elements and then compare consecutive elements (in O(nlogn) time).
>Summing the numbers didn't seem of much use. Creating another such
>array and then using the elements as indices may not be that neat of an
>approach from a memory perspective, I felt.
>
>Any other ways, folks?[/color]

OT. That said, there is missing information. If array one has
1000001 entries and array two has 999999 entries (as implied by the
description) then summing works. The sum in case one is 500005000000
[n*(n+1)/2] plus the extra element and in case two minus the missing
element. The catch is that the summation may trigger overflows. Your
task is write the code for multiple precision integer arithmetic.



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.

[Harsha Srinath]

Re: Finding Repeated and Missing Numbers

> >1.One number, in an array integers from 1 to 1,000,000 is present[color=blue][color=green]
> >twice. How can you determine which one? Can you think of a way to do
> >it using little extra memory?
> >
> >2. How would you find the only missing element in that array? Can you
> >think of a way to do it while iterating through the array only once. Is
> >overflow a problem in the solution? Why not?
> >
> >For both the problems, the solution I can think of is to sort
> >the elements and then compare consecutive elements (in O(nlogn) time).
> >Summing the numbers didn't seem of much use. Creating another such
> >array and then using the elements as indices may not be that neat of an
> >approach from a memory perspective, I felt.
> >
> >Any other ways, folks?[/color]
>
> OT. That said, there is missing information. If array one has
> 1000001 entries and array two has 999999 entries (as implied by the
> description) then summing works. The sum in case one is 500005000000
> [n*(n+1)/2] plus the extra element and in case two minus the missing
> element. The catch is that the summation may trigger overflows. Your
> task is write the code for multiple precision integer arithmetic.[/color]

Sorry. You are right, there are 1,000,001 elements and 999,999 entires
in the two cases respectively.

And if not summation, any other way??

Thanks,
Harsha Srinath

[Peter Nilsson]

Re: Finding Repeated and Missing Numbers

Harsha Srinath wrote:[color=blue]
> Athough this might not be directly relayed to C syntax, I thought some
> of you may find this an interesting problem :-
>
> 1.One number, in an array integers from 1 to 1,000,000 is present
> twice. How can you determine which one? Can you think of a way to do
> it using little extra memory?[/color]

unsigned long i, missing, sum, Sum = 1000000ul / 2 * 1000001ul;
for (i = 0, sum = 0; i < 1000001; i++)
sum += array[i];
missing = sum - Sum;
[color=blue]
> 2. How would you find the only missing element in that array? Can you
> think of a way to do it while iterating through the array only once.[/color]

unsigned long i, missing, sum, Sum = 1000000ul / 2 * 1000001ul;
for (i = 0, sum = 0; i < 999999; i++)
sum += array[i];
missing = Sum - sum;
[color=blue]
> Is overflow a problem in the solution? Why not?[/color]

Summation works fine; if you're using unsigned arithmetic, then you
can't (generally) overflow. The real problem is determining why you
have such arrays in the first place. ;)

--
Peter

[John L]

Re: Finding Repeated and Missing Numbers


"Harsha Srinath" <harshayes@gmai l.com> wrote in message news:1119851470 .946022.187520@ o13g2000cwo.goo glegroups.com.. .[color=blue]
> Athough this might not be directly relayed to C syntax, I thought some
> of you may find this an interesting problem :-
>
> 1.One number, in an array integers from 1 to 1,000,000 is present
> twice. How can you determine which one? Can you think of a way to do
> it using little extra memory?
>[/color]

The phrase "using little extra memory" makes me wonder if
the OP's friend who set this puzzle has in mind using
an array of a million bits (or a million of any data type)
and setting each bit as the corresponding number is seen.
If a bit is already set to one, then that number has been
seen before. At the end, any remaining zero bits represent
missing numbers.

--
John.

[pete]

Re: Finding Repeated and Missing Numbers

Harsha Srinath wrote:
[color=blue]
> And if not summation, any other way??[/color]

The XOR of all of the integers from 1 to 999999 is zero.

/* BEGIN new.c */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define EXTRA 998000
#define MISSING 999000
#define SIZE 1000000

int main(void)
{
long unsigned *array;
long unsigned index;
long unsigned result;
const long unsigned size = SIZE;

assert(SIZE == 1000000);
array = malloc((SIZE + 1) * sizeof *array);
if (array == NULL) {
puts("I'm tired");
exit(EXIT_FAILU RE);
}
for (index = 0; index != SIZE; ++index) {
array[index] = index + 1;
}
array[index] = EXTRA;
result = 0;
for (index = 0; index != SIZE + 1; ++index) {
result ^= array[index];
}
free(array);
printf("The extra number is %lu\n", result ^ SIZE);
array = malloc((SIZE - 1) * sizeof *array);
if (array == NULL) {
puts("I'm tired");
exit(EXIT_FAILU RE);
}
for (index = 0; index != SIZE - 1; ++index) {
array[index] = index + 1;
}
if (size > MISSING) {
array[MISSING - 1] = SIZE;
}
result = 0;
for (index = 0; index != SIZE - 1; ++index) {
result ^= array[index];
}
free(array);
printf("The missing number is %lu\n", result ^ SIZE);
return 0;
}

/* END new.c */

--
pete

[Harsha Srinath]

Re: Finding Repeated and Missing Numbers

John L wrote:[color=blue]
> "Harsha Srinath" <harshayes@gmai l.com> wrote in message news:1119851470 .946022.187520@ o13g2000cwo.goo glegroups.com.. .[color=green]
> > Athough this might not be directly relayed to C syntax, I thought some
> > of you may find this an interesting problem :-
> >
> > 1.One number, in an array integers from 1 to 1,000,000 is present
> > twice. How can you determine which one? Can you think of a way to do
> > it using little extra memory?
> >[/color]
>
> The phrase "using little extra memory" makes me wonder if
> the OP's friend who set this puzzle has in mind using
> an array of a million bits (or a million of any data type)
> and setting each bit as the corresponding number is seen.
> If a bit is already set to one, then that number has been
> seen before. At the end, any remaining zero bits represent
> missing numbers.[/color]

Yup. Thats exactly what made me also think of an possible alternative
to the summation method.

[CBFalconer]

Re: Finding Repeated and Missing Numbers

Richard Harter wrote:[color=blue]
> "Harsha Srinath" <harshayes@gmai l.com> wrote:
>[color=green]
>> Athough this might not be directly relayed to C syntax, I thought
>> some of you may find this an interesting problem :-
>>
>> 1.One number, in an array integers from 1 to 1,000,000 is present
>> twice. How can you determine which one? Can you think of a way
>> to do it using little extra memory?
>>
>> 2. How would you find the only missing element in that array? Can
>> you think of a way to do it while iterating through the array
>> only once. Is overflow a problem in the solution? Why not?
>>
>> For both the problems, the solution I can think of is to sort
>> the elements and then compare consecutive elements (in O(nlogn)
>> time). Summing the numbers didn't seem of much use. Creating
>> another such array and then using the elements as indices may not
>> be that neat of an approach from a memory perspective, I felt.
>>
>> Any other ways, folks?[/color]
>
> OT. That said, there is missing information. If array one has
> 1000001 entries and array two has 999999 entries (as implied by
> the description) then summing works. The sum in case one is
> 500005000000 [n*(n+1)/2] plus the extra element and in case two
> minus the missing element. The catch is that the summation may
> trigger overflows. Your task is write the code for multiple
> precision integer arithmetic.[/color]

As long as M is greater than 1000000 you can use modulo M
arithmetic throughout and avoid all overflows. To put it on-topic,
this is fairly automatic if using C unsigned longs.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Chris Torek]

Re: Finding Repeated and Missing Numbers

(I had to restore some of the quotes here.)

In article <1119851470.946 022.187520@o13g 2000cwo.googleg roups.com>
"Harsha Srinath" <harshayes@gmai l.com> wrote:[color=blue][color=green]
>>1.One number, in an array integers from 1 to 1,000,000 is present
>>twice. How can you determine which one? Can you think of a way to do
>>it using little extra memory?[/color][/color]
[and again, but with one number missing]

(We just had this puzzle posted.)

In article <42bf9530.45734 8408@news.sbtc. net>
From: cri@tiac.net (Richard Harter) replied:[color=blue]
>OT. That said, there is missing information. If array one has
>1000001 entries and array two has 999999 entries (as implied by the
>description) then summing works. ... The catch is that the summation
>may trigger overflows. Your task is write the code for multiple
>precision integer arithmetic.[/color]

Actually, you need not go that far. C99's "long long" is guaranteed
to hold the result without overflow (since as you noted the sum is
(1000000*100000 1)/2 or 500000500000, and LLONG_MAX must be at least
922337203685477 5807, which is considerably larger). But even C99
is not required:

In article <1119854590.603 430.155070@g44g 2000cwa.googleg roups.com>,
Harsha Srinath <harshayes@gmai l.com> wrote:[color=blue]
>Sorry. You are right, there are 1,000,001 elements and 999,999 entires
>in the two cases respectively.
>
>And if not summation, any other way??[/color]

Use "unsigned" and the properties of Galois fields. Unsigned
arithmetic implements GF(2-sup-k), where k is the number of bits
in the unsigned integer type.

unsigned sum;
size_t i;

for (sum = 0, i = 0; i < 1000001; i++)
sum += arr[i];
sum -= (1000000U * 1000001U / 2U);
printf("the missing number is %u\n", sum);

If addition is not to your liking, you can use subtraction (which
is of course just addition in disguise), or xor.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Lawrence Kirby]

Re: Finding Repeated and Missing Numbers

On Mon, 27 Jun 2005 07:16:14 +0000, Chris Torek wrote:
[color=blue]
> (I had to restore some of the quotes here.)
>
> In article <1119851470.946 022.187520@o13g 2000cwo.googleg roups.com>
> "Harsha Srinath" <harshayes@gmai l.com> wrote:[/color]

....
[color=blue][color=green]
>>And if not summation, any other way??[/color]
>
> Use "unsigned" and the properties of Galois fields. Unsigned
> arithmetic implements GF(2-sup-k), where k is the number of bits
> in the unsigned integer type.
>
> unsigned sum;
> size_t i;
>
> for (sum = 0, i = 0; i < 1000001; i++)
> sum += arr[i];
> sum -= (1000000U * 1000001U / 2U);
> printf("the missing number is %u\n", sum);
>
> If addition is not to your liking, you can use subtraction (which
> is of course just addition in disguise), or xor.[/color]

However these are all forms of summation.

Lawrence