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 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.
> >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
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
"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.
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
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.
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 ontopic,
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
(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(2supk), 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.

InRealLife: 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.
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(2supk), 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 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
   
5 posts
views
Thread by maury 
last post: by

2 posts
views
Thread by arnuld 
last post: by
          