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.
