Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
I think it can be done by using some randomized algorithm.
Divide the array into subarrays of equal size and then pick a random
element from each group.Do it 3-4 times,if random number comes out equal
for most of the times,return that element.
I haven't tried it.
On Fri, Jul 13, 2012 at 10:53 AM, Ganesh M ganesh.muniya...@gmail.comwrote:
I guess the
linkhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.htmltalks
about modified quick sort approach. Remember, if your choise of pivot
is bad everytime, this will have a worst case performance of O(n). You
should refer to Selection
Algorithmhttp://en.wikipedia.org/wiki/Selection_algorithmfor better worst
case performance.
On Wednesday, July 11, 2012 3:12:07 PM UTC+8, Navin Kumar wrote:
@sachin:
http://valis.cs.uiuc.edu/~**sariel/research/CG/applets/**
linear_prog/median.htmlhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.com
wrote:
To Mr. B
how will you find median in O(n) time? please elaborate.
On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:
I found a similar solution looking somewhere else.
The solution for this problem is:
a. There can be atmost 3 elements (only 3 distinct elements with each
repeating n/3 times) -- check for this and done. -- O(n) time.
b. There can be atmost 2 elements if not above case.
1. Find the median of the input. O(N)
2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
for output if yes}*
3. partition the array based on median found above. - O(n) --
{partition is single step in quicksort}
4. find median in left partition from (3). - O(n)
5. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
6. find median in right partition from (3). - O(n)
7. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
its 7*O(N) = O(N) solution. Constant space.
we need not check further down or recursively. {why? reason it.. its
simple}
On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:
Design an algorithm that, given a list of n elements in an array,
finds all the elements that appear more than n/3 times in the list. The
algorithm should run in linear time
( n =0 ).
You are expected to use comparisons and achieve linear time. No
hashing/excessive space/ and don't use standard linear time deterministic
selection algo.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To view this discussion on the web visit https://groups.google.com/d/**
msg/algogeeks/-/PxIJd3So3tkJhttps://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/lZKI47459WgJ.
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.
--
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology
--
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.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
I guess the
linkhttp://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.htmltalks
about modified quick sort approach. Remember, if your choise of pivot
is bad everytime, this will have a worst case performance of O(n). You
should refer to Selection
Algorithmhttp://en.wikipedia.org/wiki/Selection_algorithmfor better worst
case performance.
On Wednesday, July 11, 2012 3:12:07 PM UTC+8, Navin Kumar wrote:
@sachin:
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal
sachingoyal@gmail.comwrote:
To Mr. B
how will you find median in O(n) time? please elaborate.
On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:
I found a similar solution looking somewhere else.
The solution for this problem is:
a. There can be atmost 3 elements (only 3 distinct elements with each
repeating n/3 times) -- check for this and done. -- O(n) time.
b. There can be atmost 2 elements if not above case.
1. Find the median of the input. O(N)
2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
for output if yes}*
3. partition the array based on median found above. - O(n) --
{partition is single step in quicksort}
4. find median in left partition from (3). - O(n)
5. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
6. find median in right partition from (3). - O(n)
7. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
its 7*O(N) = O(N) solution. Constant space.
we need not check further down or recursively. {why? reason it.. its
simple}
On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:
Design an algorithm that, given a list of n elements in an array, finds
all the elements that appear more than n/3 times in the list. The
algorithm
should run in linear time
( n =0 ).
You are expected to use comparisons and achieve linear time. No
hashing/excessive space/ and don't use standard linear time deterministic
selection algo.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ.
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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/lZKI47459WgJ.
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.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
@sachin: you can find median in linear sort.
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote:
To Mr. B
how will you find median in O(n) time? please elaborate.
On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:
I found a similar solution looking somewhere else.
The solution for this problem is:
a. There can be atmost 3 elements (only 3 distinct elements with each
repeating n/3 times) -- check for this and done. -- O(n) time.
b. There can be atmost 2 elements if not above case.
1. Find the median of the input. O(N)
2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
for output if yes}*
3. partition the array based on median found above. - O(n) -- {partition
is single step in quicksort}
4. find median in left partition from (3). - O(n)
5. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
6. find median in right partition from (3). - O(n)
7. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
its 7*O(N) = O(N) solution. Constant space.
we need not check further down or recursively. {why? reason it.. its
simple}
On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:
Design an algorithm that, given a list of n elements in an array, finds
all the elements that appear more than n/3 times in the list. The algorithm
should run in linear time
( n =0 ).
You are expected to use comparisons and achieve linear time. No
hashing/excessive space/ and don't use standard linear time deterministic
selection algo.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ.
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.
--
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.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
@sachin:
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal sachingoyal@gmail.comwrote:
To Mr. B
how will you find median in O(n) time? please elaborate.
On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:
I found a similar solution looking somewhere else.
The solution for this problem is:
a. There can be atmost 3 elements (only 3 distinct elements with each
repeating n/3 times) -- check for this and done. -- O(n) time.
b. There can be atmost 2 elements if not above case.
1. Find the median of the input. O(N)
2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
for output if yes}*
3. partition the array based on median found above. - O(n) -- {partition
is single step in quicksort}
4. find median in left partition from (3). - O(n)
5. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
6. find median in right partition from (3). - O(n)
7. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
its 7*O(N) = O(N) solution. Constant space.
we need not check further down or recursively. {why? reason it.. its
simple}
On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:
Design an algorithm that, given a list of n elements in an array, finds
all the elements that appear more than n/3 times in the list. The algorithm
should run in linear time
( n =0 ).
You are expected to use comparisons and achieve linear time. No
hashing/excessive space/ and don't use standard linear time deterministic
selection algo.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ.
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.
--
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.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
can some body please explain voting algo to me .
On Wed, Jul 11, 2012 at 12:42 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@sachin:
http://valis.cs.uiuc.edu/~sariel/research/CG/applets/linear_prog/median.html
On Wed, Jul 11, 2012 at 12:28 PM, sachin goyal
sachingoyal@gmail.comwrote:
To Mr. B
how will you find median in O(n) time? please elaborate.
On Wednesday, July 11, 2012 4:01:43 AM UTC+5:30, Mr.B wrote:
I found a similar solution looking somewhere else.
The solution for this problem is:
a. There can be atmost 3 elements (only 3 distinct elements with each
repeating n/3 times) -- check for this and done. -- O(n) time.
b. There can be atmost 2 elements if not above case.
1. Find the median of the input. O(N)
2. Check if median element is repeated N/3 times or more -- O(n) - *{mark
for output if yes}*
3. partition the array based on median found above. - O(n) --
{partition is single step in quicksort}
4. find median in left partition from (3). - O(n)
5. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
6. find median in right partition from (3). - O(n)
7. check if median element is repeared n/3 times or more - O(n) *{mark
for output if yes}*
its 7*O(N) = O(N) solution. Constant space.
we need not check further down or recursively. {why? reason it.. its
simple}
On Wednesday, 27 June 2012 18:35:12 UTC-4, Navin Kumar wrote:
Design an algorithm that, given a list of n elements in an array, finds
all the elements that appear more than n/3 times in the list. The algorithm
should run in linear time
( n =0 ).
You are expected to use comparisons and achieve linear time. No
hashing/excessive space/ and don't use standard linear time deterministic
selection algo.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/PxIJd3So3tkJ.
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.
--
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.
--
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.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
My previous email got sent accidentally.. Assume if we have 90 elements and need to find 30 elements that are repeating..as per Sanjay's algo,divide it to 45 elements.. To find majority in 45 elements, the number should repeat = 23 times.. This might not be valid since the number could repeat only 15 times if it's distributed uniformly across two sub arrays.. Let me know if am wrong.. Thanks, Balaji Apologies for brevity and spelling. On Jul 2, 2012, at 11:47 PM, Balaji Subramanian balaji.subraman...@gmail.com wrote: Seems to be a nice algorithm. But won't think it would work..Majority number element should repeat for more than n/2 times.. Apologies for brevity and spelling. On Jul 2, 2012, at 1:46 PM, sanjay pandey sanjaypandey...@gmail.com wrote: i think the concept of majority elemnt can be applied here . 1.divide array into 2 halves 2.apply majority in each 3.den from d two majority found do linear counts of dere frequency?? -- 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. -- 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.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
we can use voting algorithm this.. maintain a variable count and a variable index.now make a scan for 1 to n-3.during a scan initialize count with 1 and index with 0.now if a[i]==a[index] then increment count else decrement count.when count reached 0.start again incrementing it when u get a new element and also update the indexes. now when the loop terminates then u might have got a suitable candidate.now u have to make 3 more scans in order to check the frequency of arr[index],arr[n-1] and arr[n]. On Sat, Jun 30, 2012 at 6:41 PM, saurabh singh saurab...@gmail.com wrote: @above On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0myz4OIStO8J. 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. -- 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. -- Regards Lomash Goyal * * -- 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.
Re: [algogeeks] Re: [Google] Finds all the elements that appear more than n/3 times
@above On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. On Thursday, 28 June 2012 04:05:12 UTC+5:30, Navin Kumar wrote: Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n =0 ). You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/0myz4OIStO8J. 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. -- 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.
