@saurabh. kindly use a lil bit of indentation ... ur algo is illegible. On Wed, Jul 20, 2011 at 1:28 PM, saurabh singh <[email protected]> wrote:
> Q2 o(1) space o(n) sol. > traverse through the array. > do -1*a[abs(a[i])-1] if a[abs(a[i])-1) +ve else do nothing > traverse again to check for the indexes with +ve values. > > > On Wed, Jul 20, 2011 at 1:01 PM, Shubham Maheshwari < > [email protected]> wrote: > >> let A:: ((n(n+1)/2) - sum) >> let B:: ((n(n+1)(2n+1)/6) - (sum of squares of elements)) >> >> then missing number = ((B/A) + A)/2; >> >> complexity O(n). >> space complexity O(1). >> >> On Wed, Jul 20, 2011 at 12:47 PM, saurabh singh <[email protected]>wrote: >> >>> Q1 can be solved using some simple maths....:) >>> Hint:What is the sum of first n natural numbers?"And what is the sum of >>> squares of first n natural numbers? >>> >>> >>> On Wed, Jul 20, 2011 at 12:44 PM, siva viknesh >>> <[email protected]>wrote: >>> >>>> gn array - say a >>>> >>>> hav extra array - say b - initialise all values to zero >>>> >>>> ques 1: >>>> >>>> for(i=1;i<=n;i++) >>>> { >>>> b[a[i]]++; >>>> >>>> } >>>> >>>> then traverse b array and print i, for which b[i] = 2 >>>> >>>> o(n) time & space >>>> >>>> same idea for ques 2 >>>> >>>> ....better approaches please >>>> >>>> On Jul 20, 12:11 pm, siva viknesh <[email protected]> wrote: >>>> > gn array - say a >>>> > >>>> > hav extra array - say b - initialise all values to zero >>>> > >>>> > ques 1:for(i=1;i<=n;i++) >>>> > { >>>> > b[a[i]]++; >>>> > >>>> > } >>>> > >>>> > On Jul 20, 12:07 pm, siva viknesh <[email protected]> wrote: >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > > 1.Given an array of size n. It contains numbers in the range 1 to n. >>>> > > Each number is present at least once except for 2 numbers. Find the >>>> > > missing numbers. >>>> > >>>> > > 2.Given an array of size n. It contains numbers in the range 1 to n. >>>> > > Find the numbers which aren’t present. >>>> >>>> -- >>>> 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. >>>> >>>> >>> >>> >>> -- >>> Saurabh Singh >>> B.Tech (Computer Science) >>> MNNIT ALLAHABAD >>> >>> >>> -- >>> 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. >>> >> >> >> >> -- >> Shubham Maheshwari >> ShubZz >> O.o o.O >> >> enJoY ...!!! >> >> -- >> 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. >> > > > > -- > Saurabh Singh > B.Tech (Computer Science) > MNNIT ALLAHABAD > > > -- > 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. > -- Shubham Maheshwari ShubZz O.o o.O enJoY ...!!! -- 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.
