@ankit Yup I got your point. I didn't see the algo given by dhritiman previously. I think that is better than my solution , where it fits in all cases.
Cheers Kartheek On Fri, Sep 3, 2010 at 1:32 PM, Ankit Sinha <[email protected]> wrote: > @kartheek, thanks for ur input!! Certainly, ur soln is fine but only > will cater when array is 1...n but what if it ranges for 0...n-1. The > algo given by dhritiman fits in all the scenario. but ofcourse for > given question ( 1 to 100) your mathematical approach is good. :)... > > Cheers, > Ankit Sinha!!! > > On Fri, Sep 3, 2010 at 8:14 AM, kartheek muthyala > <[email protected]> wrote:y > > > > 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]<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.
