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 <saurab...@gmail.com> 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 <sivavikne...@gmail.com>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 <sivavikne...@gmail.com> 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 <sivavikne...@gmail.com> 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 algogeeks@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.
>>
>>
>
>
> --
> 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 algogeeks@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.
>
--
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 algogeeks@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.
