Yeah The solution given by Ankit is gr8. But inorder to not destroy the array we need to go by the geek method where
Suppose x is the duplicated element and y is the missing element in the array. Multiply all the elements in the array to prod and sum all the elements in the array to sum. Divide prod with 100! that is gonna give value of x/y Subtract sum from 5050 that is gonna give 5050 + x - y Solve the two equations to get x and y. It is gonna take O(N) ideally. Cheers Kartheek On Fri, Sep 3, 2010 at 11:09 AM, Ankit Sinha <[email protected]> wrote: > @Dhritiman, It's good algo man!!!The only thing is we are destroying > the array but also that's mandatory as only o(n) complexity we are > interested in. > > As Somebody wanted the code, here I am attaching below: - > > int a[SIZE_A] = {0,2,1,4,0}; > int i = 0, dup = 0, pos = 0, t =0; > while (i< 5) > { > if (a[i] == i) > i++; > else if (a[a[i]] == a[i]) > { > dup = a[i]; > > printf ("\nduplicated element is [%d]", dup); > pos = i; > i++; > } > else > { > t= a[i]; > a[i] = a[a[i]]; > a[t] = t; > } > } > printf ("\nmissing element is [%d]", pos); > > > Cheers, > Ankit Sinha!!!! > > On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das <[email protected]> > wrote: > > @Dinesh, > > Yes, we can't apply this method, if that's not allowed. > > > > On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal <[email protected]> > wrote: > >> > >> > >> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das <[email protected]> > >> wrote: > >>> > >>> Given a array, A[1..n], do the following. > >>> Start from i=1 and try placing each number in its correct position in > the > >>> array. > >>> If the number is already in its correct position, go ahead. if (A[i] == > >>> i) , i++ > >>> else if the number was already restored to its correct position, then > it > >>> is > >>> a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup = > >>> A[i], i++ ; > >>> else > >>> swap the elements at the current index i and that at A[i]'s correct > >>> position in the array. > >>> continue this until all numbers are placed in their correct position in > >>> the array > >>> Finally, A[missing] will be dup. > >>> O(n) > >> > >> > >> @Dharitiman, good solution man. No expensive computation, no extra > memory > >> required. Only problem is it will change the input array to sorted order > >> which may not be desired. > >> > >>> > >>> On Wed, Sep 1, 2010 at 7:14 AM, Dave <[email protected]> wrote: > >>>> > >>>> Suppose that x is duplicated and y is omitted. Then the sum of the > >>>> numbers would be 5050 + x - y. Similarly, the sums of the squares of > >>>> the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of > >>>> squares of the numbers and solve the resulting equations for x and y. > >>>> > >>>> Dave > >>>> > >>>> On Aug 31, 1:57 pm, Raj Jagvanshi <[email protected]> wrote: > >>>> > There is an array having distinct 100 elements from 1 to 100 > >>>> > but by mistake some no is duplicated and a no is missed. > >>>> > Find the duplicate no and missing no. > >>>> > > >>>> > Thanks > >>>> > Raj Jagvanshi > >>>> > >>>> -- > >>>> 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]<algogeeks%[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]<algogeeks%[email protected]> > . > >>> For more options, visit this group at > >>> http://groups.google.com/group/algogeeks?hl=en. > >> > >> > >> > >> -- > >> Dinesh Bansal > >> The Law of Win says, "Let's not do it your way or my way; let's do it > the > >> best way." > >> > >> -- > >> 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]<algogeeks%[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]<algogeeks%[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]<algogeeks%[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.
