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)
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<algogeeks%2bunsubscr...@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.
