I doubt if it would work on the following example : size of array is
10, 5 and 7 are missing numbers
{1,2,3,4,6,6,6,8,9,10};
On Jul 20, 1:04 pm, Shubham Maheshwari <[email protected]>
wrote:
> @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.
