@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]. >> >>>> 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. >> >> >> >> >> >> >> >> -- >> >> 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]. >> >> 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. >> > > -- > 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.
