Yes this seems to be working.
On Feb 3, 6:50 pm, "Aravind Narayanan" <[EMAIL PROTECTED]> wrote:
> On Feb 3, 2008 10:12 PM, Ridvan Gyundogan <[EMAIL PROTECTED]> wrote:
>
>
>
> > Hi Aravind,
> > I think it will not work in this array:
> > {1,2,3,4,5,6,7,7,7,7}
> > It would give currentelem=7 and c=
Aravind Narayanan's solution involving the tournament tree does solve
the problem in n + log_2 n comparisons. It takes n-1 comparisons to
find the largest number in the array. As he explains, once you know
the largest number, you only have to check the numbers it was compared
with in the tournamen
On Feb 3, 2008 10:12 PM, Ridvan Gyundogan <[EMAIL PROTECTED]> wrote:
>
> Hi Aravind,
> I think it will not work in this array:
> {1,2,3,4,5,6,7,7,7,7}
> It would give currentelem=7 and c=3 but 7 is not repeated 6 times.
Yes, my method fails on this input.
To avoid this, after running the algo o
Hi Aravind,
I think it will not work in this array:
{1,2,3,4,5,6,7,7,7,7}
It would give currentelem=7 and c=3 but 7 is not repeated 6 times.
Best
> Init c = 1;
> Init elem = first character in the array.
> for each element in the array (other than the first one):
>if currentelem == elem:
On Feb 3, 2008 9:46 PM, Ridvan Gyundogan <[EMAIL PROTECTED]> wrote:
>
> for #2: Just create a hashtable Number-> Counts.
> Make one iteration through the whole List and make
> hashtable(Number)=hashtable(Number)+1. No comparisons so far.
> Then if size(hashtable) and compare it with (n/2+1).
>
> S
for #2: Just create a hashtable Number-> Counts.
Make one iteration through the whole List and make
hashtable(Number)=hashtable(Number)+1. No comparisons so far.
Then if size(hashtable)http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
hellow,
thanks for taking pains to replying. this is not what i meant.
i asked for n+logn comparisons. like see how much comparisons you have done
it will be over 2n. if ther are 10 numbers then you should do less than 12
comparisons
On 1/25/08, Sumedh Sakdeo <[EMAIL PROTECTED]> wrot
Hi HC
On Jan 30, 2008 12:53 AM, hc busy <[EMAIL PROTECTED]> wrote:
>
> I think there was a typo. I wanted to say its a "constant space,
> linear time algorithm" instead of "constant time linear space
> algorithm" Maybe that helps to make sense of it.
>
> Well, one must find a number that repeats
for question no. 2
median wil be the answer because repeated element is one more than the
half of the no. of element
for finding medain we can use modified quick sort which uses the fact that
we have to go only one side depending on the no. of element we found on that
side.
in general algo will
I think there was a typo. I wanted to say its a "constant space,
linear time algorithm" instead of "constant time linear space
algorithm" Maybe that helps to make sense of it.
Well, one must find a number that repeats at least twice after seeing
n/2+2 numbers, (then require the rest to be that sa
I think there was a typo. I wanted to say its a "constant space,
linear time algorithm" instead of "constant time linear space
algorithm" Maybe that helps to make sense of it.
Well, one must find a number that repeats at least twice after seeing
n/2+2 numbers, (then require the rest to be that sa
Hi HC,
Here, In this sentence
So there needs to be a number that is
repeated once after seeing n/2+2 numbers for this to be possible(and
the rest must all be the same)
How did u find this number ?
k bye
On Jan 26, 2008 3:32 AM, hc busy <[EMAIL PROTECTED]> wrote:
>
>
> #2 is weird, start by obs
On Jan 25, 2008 11:47 PM, Sumedh Sakdeo <[EMAIL PROTECTED]> wrote:
> *1) find the second biggest number in a given array of size n. you have to
> use n+logn number of searches or less
>
>
> By this you want to have a complexity less than or equal to n + log n
> rite?
>
> Consider an array { 17 ,
#2 is weird, start by observing that if you've seen n/2+2 items then
you're done.
You want n/2+1 equal numbers. So there needs to be a number that is
repeated once after seeing n/2+2 numbers for this to be possible(and
the rest must all be the same), now divide and conquer. For all
possible repe
#2 is weird, start by observing that if you've seen n/2+2 items then
you're done.
You want n/2+1 equal numbers. So there needs to be a number that is
repeated once after seeing n/2+2 numbers for this to be possible(and
the rest must all be the same), now divide and conquer. For all
possible repe
2.
keep a counter n
take the first element of the array say e and initialize the counter n=1
for each remaining number in the array
if n==0, e=current element, n=1
if current element is equal to e, n++
else n--
if n==0 there is no number
otherwise check the number of occurrences of e in the array
Regarding problem 2: If you really require o(n) rather than O(n), then
you can't even look at all of the entries in the array.
If you know that one number appears multiple times and all of the
other numbers are unique, then you do it in O(n) by looking for two
adjacent numbers that are equal. Tha
There may be a language problem here, but I think where the OP says
_searches_, he really means _comparisons_. Since O(log n) < O(n), it
doesn't make any sense to say that the complexity is O(n + log n),
because that is just O(n). Thus, I think the requirement is to use no
more than n + log n comp
*1) find the second biggest number in a given array of size n. you have to
use n+logn number of searches or less
By this you want to have a complexity less than or equal to n + log n rite?
Consider an array { 17 , 4, 3, 18 , 9 , 15, 6 }
max1 & max2 are index in array.
Iteration 1:->i=1 ( as n
19 matches
Mail list logo
