@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]<algogeeks%[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]<algogeeks%[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]<algogeeks%[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.
