a[]={1,2,3,4,5} //real a[]
a[]={1,2,3,4,3} //unreal a[]...as 2 numbers not present once...3
is 2 times and 5 is 0 times
step 1: sum=n*(n+1)/2
sum real a[]=5*6/2=15
sum unreal a[]=1+2+3+4+3=13
this means if a is 1 number nd b is 2nd then we know a-b=sum
real a[]- sum unreal a[]
step 2: now square both arrays
repeat step 1
now we know a^2-b^2=sum real a[]- sum unreal a[]
step 3: we know a-b & a^2-b^2....solve for a and b
On Tue, Jul 19, 2011 at 1:53 AM, KRISHNA <[email protected]> wrote:
> Algorithm:
>
> 1. Given array A[], Set B[], sum=0,repeatedNumb=0;
> 2. for index i to n
> B[ A[i] -1 ] = B[ A[i] -1]+1
> sum=sum+A[i]
> 3. for index i to n
> if B[i]=2
> repeatedNumb=i+1
> break;
>
> 4. Nsum=n*(n+1)/2
> 5. missingNumb=Nsum+repeatedNumb-sum
>
>
> Step-2 to3, finding the repeatedNum, complexity=O(n)+O(n)
> Step4: finding the Nsum, complexity=O(n) if formula is not used
>
>
> Thanks,
> Krishna
>
>
>
> On Jul 18, 6:26 pm, SkRiPt KiDdIe <[email protected]> wrote:
> > > @Nishant:
> >
> > >>> 1 4 5 4 5 n=5
> >
> > >>> 1 2 3 4 5
> >
> > >>> after xor i.e. your x1 answer contains (2^3^4^5).The missing elements
> are
> > >>> included in xor as well along with repeating elements.
> >
> > >>> Hope now you got it. You are giving solution for a question which i
> have
> > >>> defined in previous post. and your algo will fail when
> > >>> the final xor has no set bit i.e. same number is being repeated
> twice.
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected].
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
