Fog Creek Software
Discussion Board

sum it up

The proposed solution involves having an int value to be divided by (n-1)!  I don't know about you, but if n is a reasonable value like 200 you'll need some special work to deal with that massive int.

Much better is to use sum of squares instead of product.  That way, instead of (a+b) and (ab), you get (a+b) and (a^2+b^2).  That's reducible to (ab) -- just square (a+b), subtract (a^2+b^2), and divide by two.

One question is how does it generalize to three values?

Wei-Hwa Huang
Thursday, August 15, 2002


I guess there's a much simpler solution!

We have C=A+B, as stated in the solution.

Also, go through 1/2 the array, and find the extra number=D!

So, the repated numbers are D and C-D!

I think!

I mean, something like this:


  int size,fullSum=0,halfSum=0;
  cout<<"\nPlease enter the size of the array: \n";
  int *array=(int*)(malloc(sizeof(int)*size));
  for(int i=0;i<size+2;i++)

  int fullSumReal=(size*(size+1))/2;
  int halfSumReal=(int(size/2)*(int(size/2)+1))/2;

  int diff2=fullSum-fullSumReal;
  int diff1=halfSum-halfSumReal;

  cout<<"\nThe duplicate numbers are "<<diff1<<" and "<<diff2-diff1<<"!\n";


Please comment!

Wednesday, August 28, 2002

Hi! reffering to my previous posting, that stuff works only if the numbers are know to be divided among the halves. I guess, it's of no use then! Sorry for the bother!

Wednesday, August 28, 2002

*  Recent Topics

*  Fog Creek Home