@Dave: Can you please explain it? I am not getting you.
--
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
@Mannu. You said that the complexity of the counting sort is O(n).
Doesn't the complexity depends on the data? In particular, I'm asking
you to explain more completely how you obtain O(n) complexity with the
counting sort on a particular data set where the range of the data
depends on n. Can you
I can think of 2 methods if Hashing is not allowed.
1. Plain comparison of every element with an other element, which takes
O(n2)
2. We can sort the array, and the best we could achieve is O(nlogn) after
that use simple comparision,
like the code here : http://codepad.org/RtRbnyAN; Overall
We can use count sort for this. Its intermediate step just tell us the
frequency of each number.
and its complexity is just O(n).
--
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.
But count sort is not applicable for large number of input.In that case what
should be done?
--
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
@Mannu: Suppose that a[k] = k*k for every even value of k, and the
a[k] for odd values of k are such that the conditions of the problem
hold; i.e., every value in a[] occurs 1, 2, or 3 times, with only one
value occurring 3 times. Then what is your data structure so that the
task is O(n)?
Dave
@Gaurav Hey I forgot to say Hashing is not allowed sum thing other
then this better solution
@radha i don't think ur method works here chk out ur method
http://codepad.org/oTDNSoeu
Thanks
Shashank
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
If hashing is disallowed, then I think the best method is to sort the
data and check for consecutive triplicates. O(n log n).
Dave
On Feb 27, 6:35 am, bittu shashank7andr...@gmail.com wrote:
@Gaurav Hey I forgot to say Hashing is not allowed sum thing other
then this better solution
@radha i
i agree with dave...Sorting seems to be best method until you know something
more about type and limitations on the data present...If input has any
random numbers then sorting is best if no hashing is permitted...
On Sun, Feb 27, 2011 at 7:15 PM, Dave dave_and_da...@juno.com wrote:
If hashing
@Radha: Please explain your method further. You can use this data:
0, 1, 2, 4, 4, 5, 5, 6, 6, 6.
Dave
On Feb 26, 10:44 am, radha krishnan radhakrishnance...@gmail.com
wrote:
XOR :P
On Sat, Feb 26, 2011 at 10:11 PM, bittu shashank7andr...@gmail.com wrote:
Given an array of integers where
Kind of brute force with O(n*log(n))
map mint, int;
for( int i=0; iN; i++)
m[a[i]]++;
for each element in hashmap
if( m[i] == 3)
print i;
On Sun, Feb 27, 2011 at 3:59 AM, Dave dave_and_da...@juno.com wrote:
@Radha: Please explain your method further. You can use this data:
11 matches
Mail list logo
