main()
{
int arr[n]= {1,4,2,3,5,.......};
long SN = n*(n+1)/2;
long SN2 = n*(n+1)*(2*n+1)/6;
long Sn = 0, Sn2= 0;
long D1= 0, D2= 0;
for (int i = 0; i < n ; ++i)
{
Sn += arr[i];
Sn2 += arr[i]*arr[i];
}
D1 = SN - Sn;
D2 = SN2 - Sn2;
X = (D2 + (D1*D1)) / (2*D1);
Y = (D2 - (D1*D1)) / (2*D1);
}
On 9/16/06, Swadhin Sonowal <[EMAIL PROTECTED]> wrote:
> hi this problem is already solver previously.
> check for "Re: Finding Repeated and Missing Numbers"
>
> if X is the missing number and Y is the repeating number.
>
> then let S(N) = n*(n+1)/2
> sum of all the numbers provided be Sn
>
> ler S(N2) = n*(n+1)*(2*n+1)/6
> sum of square of all the numbers provided be Sn2
>
> now if
> D1 = S(N) - Sn
> and D2 = S(N2) - Sn2
>
> then X = (D2 + (D1*D1)) / (2*D1)
> and Y = (D2 - (D1*D1)) / (2*D1)
>
> So its a order O(n) solution.
>
> regards
> swadhin
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
