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