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