[algogeeks] Re: Finding the mode in a set of integers
Can you illustrate it with an example ? How are you deciding the pivot for partitioning the array ? How the middle element can be the mode of the array ? Regards Gauri On Apr 14, 5:39 pm, vivek bijlwan viv...@gmail.com wrote: complexity : On) extra - memory required : no have the first iteration of quick sort. return the middle element. On Wed, Apr 14, 2010 at 4:14 PM, Gauri gauri...@gmail.com wrote: Say If I have an array of 1,000 32-bit integers .And one of the value is occuring 501 number of times or more in the array. Can someone help me devise an efficient algorithm for the same ? Thanks Regards Gauri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Finding the mode in a set of integers
It cannot just be partitioned in such a manner that the middle element is *always *the mode ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Apr 15, 2010 at 11:23 AM, Gauri gauri...@gmail.com wrote: Can you illustrate it with an example ? How are you deciding the pivot for partitioning the array ? How the middle element can be the mode of the array ? Regards Gauri On Apr 14, 5:39 pm, vivek bijlwan viv...@gmail.com wrote: complexity : On) extra - memory required : no have the first iteration of quick sort. return the middle element. On Wed, Apr 14, 2010 at 4:14 PM, Gauri gauri...@gmail.com wrote: Say If I have an array of 1,000 32-bit integers .And one of the value is occuring 501 number of times or more in the array. Can someone help me devise an efficient algorithm for the same ? Thanks Regards Gauri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Finding the mode in a set of integers
@rohit : can you give me any counter examples? PS: one value is occuring =501 times. On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: It cannot just be partitioned in such a manner that the middle element is *always *the mode ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Thu, Apr 15, 2010 at 11:23 AM, Gauri gauri...@gmail.com wrote: Can you illustrate it with an example ? How are you deciding the pivot for partitioning the array ? How the middle element can be the mode of the array ? Regards Gauri On Apr 14, 5:39 pm, vivek bijlwan viv...@gmail.com wrote: complexity : On) extra - memory required : no have the first iteration of quick sort. return the middle element. On Wed, Apr 14, 2010 at 4:14 PM, Gauri gauri...@gmail.com wrote: Say If I have an array of 1,000 32-bit integers .And one of the value is occuring 501 number of times or more in the array. Can someone help me devise an efficient algorithm for the same ? Thanks Regards Gauri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Finding the mode in a set of integers
say u choose the last value as pivot 1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4 4 is your pivot try out -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Apr 15, 2010 at 5:26 PM, vivek bijlwan viv...@gmail.com wrote: @rohit : can you give me any counter examples? PS: one value is occuring =501 times. On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: It cannot just be partitioned in such a manner that the middle element is *always *the mode ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Thu, Apr 15, 2010 at 11:23 AM, Gauri gauri...@gmail.com wrote: Can you illustrate it with an example ? How are you deciding the pivot for partitioning the array ? How the middle element can be the mode of the array ? Regards Gauri On Apr 14, 5:39 pm, vivek bijlwan viv...@gmail.com wrote: complexity : On) extra - memory required : no have the first iteration of quick sort. return the middle element. On Wed, Apr 14, 2010 at 4:14 PM, Gauri gauri...@gmail.com wrote: Say If I have an array of 1,000 32-bit integers .And one of the value is occuring 501 number of times or more in the array. Can someone help me devise an efficient algorithm for the same ? Thanks Regards Gauri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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.
[algogeeks] Re: Finding the mode in a set of integers
I feel gaurav's solution does it in O(n) time cons space
but there is a case that when there is no element with n/2+1
appearances the method might fail(eg 1 1 1 2 3 4 and in many other
cases as well...)
but as the problem states that there is atleast 1 element with n/2+1
appearancesthis algo provides the answer to above question.
On Apr 15, 1:09 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
*FINAL SOLUTION* :
I gave a second thought :
A large amount of space(but finite constant and bounded and within practical
limits) will eventually be required for my hashing based solution to be
worst case O(n).
So this problem has an linear time solution..
BUT can we do better in terms of space maintaining the time complexity?
Well, I claim that we cannot ! :(
Can anyone disprove/prove that we can do better ??
I don't think the 2 solutions above work
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14
On Thu, Apr 15, 2010 at 10:13 AM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
the implementation of the hashmap in prev soln(to achieve constant time) is
non-trivial and is based on some exercise of Cormen.
better and simple:
Think of these points as nodes of the graph
use the UnionFind(quickunion) data structure... and everytime a union is
done add 1 to the component united.
find the one with count500
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Thu, Apr 15, 2010 at 9:16 AM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
I agree But that worst case will never come here. There are
between 2 and 500 keys. And all keys are different So how would
the worst case come??
On 4/14/10, gaurav kishan gauravkis...@gmail.com wrote:
This will be done in one pass i.e O(n).
On Wed, Apr 14, 2010 at 10:17 PM, gaurav kishan
gauravkis...@gmail.comwrote:
Can everyone check this out and let me the issues ?
int[] i=new
int[]{11,2,3,11,4,11,76,11,11,65,11,44,78,11,13,11,79,11,11,11,56};
int count=1,element=i[0];
for(int j=1;ji.length;j++)
{
if(element==i[j])
count++;
else
{
count--;
if(count==0)
{
element=i[j];
count=1;
}
}
}
System.out.println(Mode is +element);
}
Regards,
Gaurav Kishan
On Wed, Apr 14, 2010 at 10:01 PM, sharad kumar
aryansmit3...@gmail.comwrote:
ya over here its 501 rite?
On Wed, Apr 14, 2010 at 8:24 PM, Prakhar Jain prakh...@gmail.com
wrote:
If m thinking right,
That works if mode occurs =n/2 times in the array
Best,
Prakhar Jain
http://web.iiit.ac.in/~prakharjain/
On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar
aryansmit3...@gmail.com
wrote:
can we make use of majority VOTE ALGORITHM?
On Wed, Apr 14, 2010 at 4:14 PM, Gauri gauri...@gmail.com wrote:
Say If I have an array of 1,000 32-bit integers .And one of the
value
is occuring 501 number of times or more in the array. Can someone
help
me devise an efficient algorithm for the same ?
Thanks Regards
Gauri
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googleg
roups.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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googleg
roups.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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googleg
roups.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
Re: [algogeeks] Re: Finding the mode in a set of integers
@rohit : thats more than 1000 elements in the array On Thu, Apr 15, 2010 at 7:48 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: say u choose the last value as pivot 1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4 4 is your pivot try out -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Thu, Apr 15, 2010 at 5:26 PM, vivek bijlwan viv...@gmail.com wrote: @rohit : can you give me any counter examples? PS: one value is occuring =501 times. On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: It cannot just be partitioned in such a manner that the middle element is *always *the mode ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Thu, Apr 15, 2010 at 11:23 AM, Gauri gauri...@gmail.com wrote: Can you illustrate it with an example ? How are you deciding the pivot for partitioning the array ? How the middle element can be the mode of the array ? Regards Gauri On Apr 14, 5:39 pm, vivek bijlwan viv...@gmail.com wrote: complexity : On) extra - memory required : no have the first iteration of quick sort. return the middle element. On Wed, Apr 14, 2010 at 4:14 PM, Gauri gauri...@gmail.com wrote: Say If I have an array of 1,000 32-bit integers .And one of the value is occuring 501 number of times or more in the array. Can someone help me devise an efficient algorithm for the same ? Thanks Regards Gauri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Finding the mode in a set of integers
Remove as many 3's that would make it 1000. The example still holds @gauri: the logic is that if your pivot is greater than all numbers till middle then it would not effect the middle element. Hence if middle element is not the mode in the given array, the answerwould be wrong. On 4/15/10, vivek bijlwan viv...@gmail.com wrote: @rohit : thats more than 1000 elements in the array On Thu, Apr 15, 2010 at 7:48 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: say u choose the last value as pivot 1 1 1 1 1 1 1 (499 times) 2 2 2 2 1 1 3 3 3 3 (499 times) 4 4 is your pivot try out -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Thu, Apr 15, 2010 at 5:26 PM, vivek bijlwan viv...@gmail.com wrote: @rohit : can you give me any counter examples? PS: one value is occuring =501 times. On Thu, Apr 15, 2010 at 5:12 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: It cannot just be partitioned in such a manner that the middle element is *always *the mode ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Thu, Apr 15, 2010 at 11:23 AM, Gauri gauri...@gmail.com wrote: Can you illustrate it with an example ? How are you deciding the pivot for partitioning the array ? How the middle element can be the mode of the array ? Regards Gauri On Apr 14, 5:39 pm, vivek bijlwan viv...@gmail.com wrote: complexity : On) extra - memory required : no have the first iteration of quick sort. return the middle element. On Wed, Apr 14, 2010 at 4:14 PM, Gauri gauri...@gmail.com wrote: Say If I have an array of 1,000 32-bit integers .And one of the value is occuring 501 number of times or more in the array. Can someone help me devise an efficient algorithm for the same ? Thanks Regards Gauri -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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. -- Sent from my mobile device -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this
