@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 <dedhriti...@gmail.com> 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 <bansal...@gmail.com> wrote: >> >> >> On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das <dedhriti...@gmail.com> >> 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 <dave_and_da...@juno.com> 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 <raj.jagvan...@gmail.com> 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 algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com. >>>> 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 algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com. >>> 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 algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.