i don't think the repeat number is limited to only one.
Anyway, it's a program problem, not a math one.
2006/8/24, Kamlesh <[EMAIL PROTECTED]>:
Hi all,
Suppose
a -repeated element.
b -missing element.
S -Sum of 1-N elements=N*(N+1)/2.
M -Product of 1-N elements=N!.
S1-Sum of elements in array
M1-Product of elements in array.
So, a/b=M1/M and |a-b|=|S-S1|.
Using these two equations we get
b = M*|S-S1|/|M-M1|.
a = M1*b/M = M1|S-S1|/|M-M1|.
This surely can be done in O(n) and code for the same goes like
S1=0; M1=1; M=1; S=N*(N+1)/2.
for(i=0;i<N;i++)
{
S1+=arr[i];
M1*=arr[i];
M*=(i+1);
}
t1=abs(S-S1); t2=abs(M1-M);
Repeated_element = M1*t1/t2;
Missing_element = M*t1/t2;
Thanks,
Kamlesh
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
