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
-~--~~~~--~~--~--~---
You can google for "big integer" libraries written in C if you need
support for complicated operations. Here is one way you can do it.
Define a big integer to be an array of digits, then implement the
operations that you need. Addition/multiplication by a constant/
division by a constant are strai
hellow,
i am doing a program which deals with 128 bit numbers.i want to
store a 128 bit in a variable, as we know all the data types in c offer less
than 80 bits. now how do i create a 128 bit data type for my program.
--~--~-~--~~~---~--~~
You received thi
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
