468,121 Members | 1,447 Online

# Finding Repeated and Missing Numbers

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

Nov 15 '05 #1
9 11338 On 26 Jun 2005 22:51:10 -0700, "Harsha Srinath" <ha*******@gmail.com>
wrote:
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?

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, cr*@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
Nov 15 '05 #2
> >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?

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.

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

Nov 15 '05 #3
Harsha Srinath wrote:
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?
unsigned long i, missing, sum, Sum = 1000000ul / 2 * 1000001ul;
for (i = 0, sum = 0; i < 1000001; i++)
sum += array[i];
missing = sum - Sum;
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.
unsigned long i, missing, sum, Sum = 1000000ul / 2 * 1000001ul;
for (i = 0, sum = 0; i < 999999; i++)
sum += array[i];
missing = Sum - sum;
Is overflow a problem in the solution? Why not?

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

Nov 15 '05 #4

"Harsha Srinath" <ha*******@gmail.com> wrote in message news:11**********************@o13g2000cwo.googlegr oups.com...
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?

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.
Nov 15 '05 #5
Harsha Srinath wrote:
And if not summation, any other way??

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_FAILURE);
}
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_FAILURE);
}
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
Nov 15 '05 #6
John L wrote:
"Harsha Srinath" <ha*******@gmail.com> wrote in message news:11**********************@o13g2000cwo.googlegr oups.com...
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?

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.

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

Nov 15 '05 #7
Richard Harter wrote:
"Harsha Srinath" <ha*******@gmail.com> wrote:
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?

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.

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.com, 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
Nov 15 '05 #8
(I had to restore some of the quotes here.)

In article <11**********************@o13g2000cwo.googlegroups .com>
"Harsha Srinath" <ha*******@gmail.com> wrote:
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?
[and again, but with one number missing]

(We just had this puzzle posted.)

In article <42****************@news.sbtc.net>
From: cr*@tiac.net (Richard Harter) replied: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.
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*1000001)/2 or 500000500000, and LLONG_MAX must be at least
9223372036854775807, which is considerably larger). But even C99
is not required:

In article <11**********************@g44g2000cwa.googlegroups .com>,
Harsha Srinath <ha*******@gmail.com> wrote: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??

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.
Nov 15 '05 #9
On Mon, 27 Jun 2005 07:16:14 +0000, Chris Torek wrote:
(I had to restore some of the quotes here.)

In article <11**********************@o13g2000cwo.googlegroups .com>
"Harsha Srinath" <ha*******@gmail.com> wrote:

....
And if not summation, any other way??

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.

However these are all forms of summation.

Lawrence

Nov 15 '05 #10

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 3 posts views Thread by David Berry | last post: by 25 posts views Thread by Subra | last post: by 1 post views Thread by Silver8 | last post: by 8 posts views Thread by Engrm | last post: by 20 posts views Thread by kpfunf | last post: by 5 posts views Thread by maury | last post: by 2 posts views Thread by arnuld | last post: by reply views Thread by initdebug | last post: by 5 posts views Thread by SwissProgrammer | last post: by reply views Thread by LessComplexity | last post: by 1 post views Thread by Madjia22 | last post: by 2 posts views Thread by RaGa68 | last post: by 1 post views Thread by xerxes | last post: by 4 posts views Thread by mshakeelattari | last post: by reply views Thread by krisrajz | last post: by reply views Thread by ravipankaj | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.