[algogeeks] Finding the mode in a set of integers
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding all prime less than 10^8
The Sieve of Eratosthenes is best for finding prime
On Mon, Apr 12, 2010 at 10:58 AM, BlackdiamonD patidarc...@gmail.comwrote:
thank kartik thanks but it was with lot of optimized code i was unable to
understand though i have changed my code more know it is taking around 8 to
8.5 seconds in my computer but still i am getting TLE on server
#includestdio.h
#define ten8 (1)
const int mod=32;
unsigned int M[ten8/mod];
int main()
{
int half=1, i,j,x=1;
int y=ten8/mod;
freopen(output.txt,wt,stdout);
for ( i = 0;i y;i++)
M[i] = 0;
printf(2\n);
for ( i = 3;i ten8;i+=2)
{
int a=i/mod,b=i%mod;
if (((M[a]b)1)==0)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j/mod] =M[j/mod]|(1(j%mod));
}
}
}
}
On Sun, Apr 11, 2010 at 7:20 AM, Karthik Reddy
karthik.gin...@gmail.comwrote:
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
take a look at this link . The running time is less than 2 sec for 10^8.
On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond patidarc...@gmail.comwrote:
i have an problem on SPOJ to find all the prime less than 10^8
https://www.spoj.pl/problems/TDPRIMES/
i am using sieve of erastosthenes algorithm to find primes
my code is taking in my machine around 10.9 to 11.2 seconds
and time limit is 10 second how i can change my code or any diff
logic..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
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.
--
Ram Karthik Reddy Ginuga
karthik.ginuga[at]gmail.com
CCNA,MCP
Mozilla Campus Ambassador
SPOJ world rank #1088
http://www.spoj.pl/users/karthu/
(91)40 27425999
(91)9247818845
--
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.
--
BL/\CK_D!AMOND
--
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.
--
Ashish Mishra
http://ashishmishra.weebly.com/
--
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.
My+Sign.JPG
Re: [algogeeks] store fractional numbers with high precision
there is a problem to find first K digits of no. N^N , where N can be as large as 10^9. so, the algo goes like, take fractional part(f) of Nlog10(N). and temp=pow(10,f), result =(long )10^k * temp. I want to assure myself that f has enough fractional part precision so that at most first 9 digits can be correctly found. I more doubt , does the maximum value of any type assures that it can hold all intermediate value. my ques is the maximum number of digits after decimal a type can hold. Can any1 clear my doubt related to long double that i initially asked. Help appreciated. *Apologies for any stupidity. On Wed, Apr 14, 2010 at 6:31 AM, sharad kumar aryansmit3...@gmail.comwrote: Do u have to use only C++ ,cant u use scripting languages like Pythonwhere precision is very good in Python..esp wen u use Si-Py On Tue, Apr 13, 2010 at 10:10 PM, Himanshu Aggarwal lkml.himan...@gmail.com wrote: I think it should depend on the underlying architecture, on how it stores the floating data types In case floats and double are implemented using IEEE 754, then floats have 8 bits for precision and double have 11 bits for precision. Normally the exponents are biased, which means that for float it ranges from 2^(-127) to 2^(+ 127) and for double it ranges from 2^(-1024) to 2^(+1024). ~Himanshu Aggarwal On Tue, Apr 13, 2010 at 6:10 AM, Anil C R cr.a...@gmail.com wrote: correct me if I'm wrong but, float has a precision of around 8 digits. and double 16 digits... if you want arbitrary precision floating point numbers, try GNU BigNum library... Anil On Mon, Apr 12, 2010 at 9:54 PM, Himanshu Aggarwal lkml.himan...@gmail.com wrote: On Sun, Apr 11, 2010 at 6:55 PM, GentLeBoY vikrantsing...@gmail.comwrote: how to store fractional numbers with a fractional part having 25-30 digits after decimal place, does long double has the same precision as double?. 1 more prob. format specifier for long double is %lf and same for double, so if i write long double a; scanf(%lf,a); a=a*2; printf(%lf,a); why is the output -2. ? -- 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. Float has single precision. double has double precision. Long double has extended precision. For your requirement, even a float would suffice. check out the value of FLT_MAX . It is of the order of 10^37. ~Himanshu Aggarwal -- 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. -- Vikrant Singh -- 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: Implement a queue using a stack
if two stacks then possible otherwise i dont think so On Mon, Apr 12, 2010 at 11:39 PM, Dheeraj Jain dheerajj...@gmail.comwrote: Here is code and explanation http://geeksforgeeks.org/?p=5009 On Sat, Apr 10, 2010 at 10:18 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: hmm... that can always be done ! -- 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 Wed, Mar 24, 2010 at 6:24 PM, Dave dave_and_da...@juno.com wrote: Please post your results. I'd like to study your algorithm. On Mar 23, 11:15 pm, chitta koushik koushik.infin...@gmail.com wrote: yeah i understand that . still wanted to attempt writing a recursive reverse() stack operation. On Wed, Mar 24, 2010 at 9:21 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Even when you are writing a recursive function.. you are not using one stack. One stack is yours. Other used for recursion. Making queue from a single stack = Making turing machine from CFG. -Rohit On Wed, Mar 24, 2010 at 9:18 AM, chitta koushik koushik.infin...@gmail.com wrote: Can we implement it using a single stack by writing a recursive reverse stack operation ? On Tue, Mar 23, 2010 at 10:18 AM, Sundeep Singh singh.sund...@gmail.comwrote: Thanks Dave, I didn't think about this... definitely better! Sundeep. On Mon, Mar 22, 2010 at 9:08 PM, Dave dave_and_da...@juno.com wrote: Better still. To enqueue: push onto stack A. For dequeuing: If stack B is empty, pop all items from stack A and push onto stack B. Then pop stack B. There is no need to push remaining items back to stack A. As every item passes through the queue, it is pushed onto stack A, then popped from stack A and pushed onto stack B, and finally popped from stack B. The time is roughly twice the time required for a direct implementation of a queue. There is room for a little optimization if both stacks are empty when enquing, as you can push the item directly onto stack B. Furthermore, when popping from stack A and pushing onto stack B, you don't need to push the last item popped, as it is the return value. Dave On Mar 22, 9:29 am, Sundeep Singh singh.sund...@gmail.com wrote: Hey Brian, Better still, for inserting in queue, just keep pushing onto the stack A. You need stack B only for dequeuing: for dequeuing, push all items into stack B, pop as many as you want from stack B and then push back all remaining items in stack A. Regards, Sundeep. On Mon, Mar 22, 2010 at 6:56 PM, Brian brianfo...@gmail.com wrote: How is it possible to implement a queue using a stack only? Interesting, but tricky... You need two stacks as Prakhar stated... In general, if you have Stack A and Stack B, you should keep all the items in stack A and then use stack B for processing. For example to insert an item: 1. Pop all the items from A and then push them into B (this should push the items into Stack B in reverse order) 2. Insert the new item into A 3. Pop all the items in B and push them back into A (again this will push them back into Stack B in reverse order) Running time should be O(1)+O(2n), which is O(n) for larger values of n - which is not good... To retrieve an item, pop the first item in stack A Hope this helps - Regards B On 3/22/2010 4:55 AM, Prakhar Jain wrote: By a do u mean a single stack ? Otherwise if you use 2 its v simple Best, Prakhar Jain http://web.iiit.ac.in/~prakharjain/http://web.iiit.ac.in/%7Eprakharjain/ http://web.iiit.ac.in/%7Eprakharjain/ http://web.iiit.ac.in/%7Eprakharjain/ On Mon, Mar 22, 2010 at 12:56 AM, Pushpesh Gupta pushpes...@gmail.comwrote: How is it possible to implement a queue using a stack only? -- 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 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
Re: [algogeeks] Finding the mode in a set of integers
O(n log n) will be trivial. O(n) is required at any cost. (Consider the case with 501 1s and 499 0's) Ok, so u can make a hashmap with your integer as keys and frequency as the value. No of keys will be between 2 and 500. (= Traversing through takes O(n) ) You will have to traverse the array exactly once = O(n) = O(n) solution. And it cannot be made better ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 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.
[algogeeks] Re: First k smallest elements
Sure, we can build a heap. But what's the point. Already, an O(n) solution has been identified, using the median of medians algorithm. A heap would be O(n ln k). Dave On Apr 14, 4:25 am, Ashish Mishra amishra@gmail.com wrote: can't we build a min-heap (kinda opposite of max-heap) ?? On Wed, Apr 14, 2010 at 8:42 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Not linear in worst case On 4/13/10, souri datta souri.isthe...@gmail.com wrote: what about the algorithm which mimics the Quick Sort and deals with only one partition( as in Coremen) ? On Tue, Apr 13, 2010 at 9:11 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: So tell me something else which works in O(n) On 4/12/10, souri datta souri.isthe...@gmail.com wrote: Why only median of median? On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Find the kth element using order statistics - O(n) As far as i know , u will have to use median of medians selection algorithm for this... Rest is fine.. -- 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 Mon, Apr 12, 2010 at 3:20 PM, souri datta souri.isthe...@gmail.com wrote: Steps: 1. Find the kth element using order statistics - O(n) 2. In one pass over the array, get all the elems less than the kth element. Let me know if this is not correct. On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: I have already given an O(n) solution. See above ! The BST solution is O(nlogn) but is practically more nice. :) -- 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 Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: are yaar... i meant BST... i thought that was obvious ! sry if i confused you @rohit It's ok.Actually in this group people come up with very different and non-common solutions so its risky to take things 'obviously'. Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) [for rotating n times]=O(nlogn) . Till now best algo we have is using heaps which give rise to complexity = O(n+klogn) Please pass on algos having better runtime complexity. -- 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 Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Hey rohit.You were referring to Binary tree.Search keyword was missing.Because rotation makes no sense in binary tree.Please note binary tree and BST are different. On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Read the slides i uploaded. They explain what rotation does in a BST. Also you might like to refer to Red Black Trees in CLRS that chapter explains rotations. -- 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 Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: but still the binary tree solution is of more practical use.i will explain the solution once i reach my comp On 4/11/10, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Time complexity is O(n log n). But the last solution I gave has O(n). What did u not understand abt thesolution @Rohit Please explain how that Binary tree solution works. -- 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 Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: On 11 April 2010 10:46, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Construct a binary tree from the data (maintain the size of subtree under each node). Do rotations till the left subtree does not have size k. Rotation is a constant time operation.
Re: [algogeeks] Re: First k smallest elements
exactly ! But the point is Though i did it in o(n), still the constant will be too high to use.(practically the bst solution will work better for n10^20 So can we do better?? On 4/14/10, Dave dave_and_da...@juno.com wrote: Sure, we can build a heap. But what's the point. Already, an O(n) solution has been identified, using the median of medians algorithm. A heap would be O(n ln k). Dave On Apr 14, 4:25 am, Ashish Mishra amishra@gmail.com wrote: can't we build a min-heap (kinda opposite of max-heap) ?? On Wed, Apr 14, 2010 at 8:42 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Not linear in worst case On 4/13/10, souri datta souri.isthe...@gmail.com wrote: what about the algorithm which mimics the Quick Sort and deals with only one partition( as in Coremen) ? On Tue, Apr 13, 2010 at 9:11 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: So tell me something else which works in O(n) On 4/12/10, souri datta souri.isthe...@gmail.com wrote: Why only median of median? On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Find the kth element using order statistics - O(n) As far as i know , u will have to use median of medians selection algorithm for this... Rest is fine.. -- 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 Mon, Apr 12, 2010 at 3:20 PM, souri datta souri.isthe...@gmail.com wrote: Steps: 1. Find the kth element using order statistics - O(n) 2. In one pass over the array, get all the elems less than the kth element. Let me know if this is not correct. On Mon, Apr 12, 2010 at 1:57 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: I have already given an O(n) solution. See above ! The BST solution is O(nlogn) but is practically more nice. :) -- 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 Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: are yaar... i meant BST... i thought that was obvious ! sry if i confused you @rohit It's ok.Actually in this group people come up with very different and non-common solutions so its risky to take things 'obviously'. Rotation algo has a complexity of O(nlogn)[for constructing a BST] +O(n) [for rotating n times]=O(nlogn) . Till now best algo we have is using heaps which give rise to complexity = O(n+klogn) Please pass on algos having better runtime complexity. -- 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 Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Hey rohit.You were referring to Binary tree.Search keyword was missing.Because rotation makes no sense in binary tree.Please note binary tree and BST are different. On Mon, Apr 12, 2010 at 12:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Read the slides i uploaded. They explain what rotation does in a BST. Also you might like to refer to Red Black Trees in CLRS that chapter explains rotations. -- 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 Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: but still the binary tree solution is of more practical use.i will explain the solution once i reach my comp On 4/11/10, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: On Sun, Apr 11, 2010 at 9:56 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Time complexity is O(n log n). But the last solution I gave has O(n). What did u not understand abt thesolution @Rohit Please explain how that Binary tree solution works. -- 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 Sun, Apr 11, 2010 at 11:00 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: On 11
Re: [algogeeks] Finding the mode in a set of integers
Sorry i meant This soln is going to take O(n) expected time. and not This soln is going to take O(1) expected time. On Wed, Apr 14, 2010 at 6:43 PM, rizwan hudda rizwanhu...@gmail.com wrote: O(n) is indeed the lower bound of any algorithm on this problem :) Yes. O(nlogn) is trivial. Sort the given array. And count the number of occurrences of each element. For some element u ll get it as 501. U have found that element! And about the hashmap based solution. Hashmap internally uses a tree based structure. So, your 'n' insertion operations will indeed take O(n*logn) time. I guess you meant using Hashing technique. i,e Using a hash function to add elements to the bucket array. And then check all the buckets with more than 500 elements [ since there can be collisions ]. And in one of them there will be 501 same elements. This soln is going to take O(1) expected time. The open question is to look for an algorithm to find the mode in O(n) worst case time complexity. On Wed, Apr 14, 2010 at 6:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: O(n log n) will be trivial. O(n) is required at any cost. (Consider the case with 501 1s and 499 0's) Ok, so u can make a hashmap with your integer as keys and frequency as the value. No of keys will be between 2 and 500. (= Traversing through takes O(n) ) You will have to traverse the array exactly once = O(n) = O(n) solution. And it cannot be made better ! -- 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 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda -- Thanks and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda -- 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
How about bucket sort. On Wed, Apr 14, 2010 at 6:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: O(n log n) will be trivial. O(n) is required at any cost. (Consider the case with 501 1s and 499 0's) Ok, so u can make a hashmap with your integer as keys and frequency as the value. No of keys will be between 2 and 500. (= Traversing through takes O(n) ) You will have to traverse the array exactly once = O(n) = O(n) solution. And it cannot be made better ! -- 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 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.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
O(n) is indeed the lower bound of any algorithm on this problem :) Yes. O(nlogn) is trivial. Sort the given array. And count the number of occurrences of each element. For some element u ll get it as 501. U have found that element! And about the hashmap based solution. Hashmap internally uses a tree based structure. So, your 'n' insertion operations will indeed take O(n*logn) time. I guess you meant using Hashing technique. i,e Using a hash function to add elements to the bucket array. And then check all the buckets with more than 500 elements [ since there can be collisions ]. And in one of them there will be 501 same elements. This soln is going to take O(1) expected time. The open question is to look for an algorithm to find the mode in O(n) worst case time complexity. On Wed, Apr 14, 2010 at 6:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: O(n log n) will be trivial. O(n) is required at any cost. (Consider the case with 501 1s and 499 0's) Ok, so u can make a hashmap with your integer as keys and frequency as the value. No of keys will be between 2 and 500. (= Traversing through takes O(n) ) You will have to traverse the array exactly once = O(n) = O(n) solution. And it cannot be made better ! -- 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 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda -- 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
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 . 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
You are being specific to some programming lang. , I guess. Hashmap refers to hashing in general. On 4/14/10, rizwan hudda rizwanhu...@gmail.com wrote: O(n) is indeed the lower bound of any algorithm on this problem :) Yes. O(nlogn) is trivial. Sort the given array. And count the number of occurrences of each element. For some element u ll get it as 501. U have found that element! And about the hashmap based solution. Hashmap internally uses a tree based structure. So, your 'n' insertion operations will indeed take O(n*logn) time. I guess you meant using Hashing technique. i,e Using a hash function to add elements to the bucket array. And then check all the buckets with more than 500 elements [ since there can be collisions ]. And in one of them there will be 501 same elements. This soln is going to take O(1) expected time. The open question is to look for an algorithm to find the mode in O(n) worst case time complexity. On Wed, Apr 14, 2010 at 6:33 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: O(n log n) will be trivial. O(n) is required at any cost. (Consider the case with 501 1s and 499 0's) Ok, so u can make a hashmap with your integer as keys and frequency as the value. No of keys will be between 2 and 500. (= Traversing through takes O(n) ) You will have to traverse the array exactly once = O(n) = O(n) solution. And it cannot be made better ! -- 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 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda -- 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 group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the mode in a set of integers
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.comwrote: 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 . 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 all prime less than 10^8
thankx for u r reply.in my code i implemented Sieve of Eratosthenesthat
but some type of optimization were required that i have done...got accepted.
On Wed, Apr 14, 2010 at 2:57 PM, Ashish Mishra amishra@gmail.comwrote:
The Sieve of Eratosthenes is best for finding prime
On Mon, Apr 12, 2010 at 10:58 AM, BlackdiamonD patidarc...@gmail.comwrote:
thank kartik thanks but it was with lot of optimized code i was unable to
understand though i have changed my code more know it is taking around 8 to
8.5 seconds in my computer but still i am getting TLE on server
#includestdio.h
#define ten8 (1)
const int mod=32;
unsigned int M[ten8/mod];
int main()
{
int half=1, i,j,x=1;
int y=ten8/mod;
freopen(output.txt,wt,stdout);
for ( i = 0;i y;i++)
M[i] = 0;
printf(2\n);
for ( i = 3;i ten8;i+=2)
{
int a=i/mod,b=i%mod;
if (((M[a]b)1)==0)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j/mod] =M[j/mod]|(1(j%mod));
}
}
}
}
On Sun, Apr 11, 2010 at 7:20 AM, Karthik Reddy
karthik.gin...@gmail.comwrote:
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
take a look at this link . The running time is less than 2 sec for 10^8.
On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond patidarc...@gmail.comwrote:
i have an problem on SPOJ to find all the prime less than 10^8
https://www.spoj.pl/problems/TDPRIMES/
i am using sieve of erastosthenes algorithm to find primes
my code is taking in my machine around 10.9 to 11.2 seconds
and time limit is 10 second how i can change my code or any diff
logic..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
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.
--
Ram Karthik Reddy Ginuga
karthik.ginuga[at]gmail.com
CCNA,MCP
Mozilla Campus Ambassador
SPOJ world rank #1088
http://www.spoj.pl/users/karthu/
(91)40 27425999
(91)9247818845
--
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.
--
BL/\CK_D!AMOND
--
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.
--
Ashish Mishra
http://ashishmishra.weebly.com/
--
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.
--
BL/\CK_D!AMOND
--
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.
My+Sign.JPG
Re: [algogeeks] Finding the mode in a set of integers
Majority vote algorithm O(n) seems to be a good approach. http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar aryansmit3...@gmail.comwrote: 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 . 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. -- Thanks Regards, - NMN -- 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
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/http://web.iiit.ac.in/%7Eprakharjain/ On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar aryansmit3...@gmail.comwrote: 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 . 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
@rizwan : Think!!. *my algorithm is worst case O(n)*.. no doubt ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 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/http://web.iiit.ac.in/%7Eprakharjain/ On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar aryansmit3...@gmail.comwrote: 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 . 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
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.comwrote:
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
.
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
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
.
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] Please Help!!! store fractional numbers with high precision
On Wed, Apr 14, 2010 at 1:22 PM, vikrant singh vikrantsing...@gmail.comwrote: there is a problem to find first K digits of no. N^N , where N can be as large as 10^9. so, the algo goes like, take fractional part(f) of Nlog10(N). and temp=pow(10,f), result =(long )10^k * temp. I want to assure myself that f has enough fractional part precision so that at most first 9 digits can be correctly found. I more doubt , does the maximum value of any type assures that it can hold all intermediate value. my ques is the maximum number of digits after decimal a type can hold. Can any1 clear my doubt related to long double that i initially asked. Help appreciated. *Apologies for any stupidity. On Wed, Apr 14, 2010 at 6:31 AM, sharad kumar aryansmit3...@gmail.comwrote: Do u have to use only C++ ,cant u use scripting languages like Pythonwhere precision is very good in Python..esp wen u use Si-Py On Tue, Apr 13, 2010 at 10:10 PM, Himanshu Aggarwal lkml.himan...@gmail.com wrote: I think it should depend on the underlying architecture, on how it stores the floating data types In case floats and double are implemented using IEEE 754, then floats have 8 bits for precision and double have 11 bits for precision. Normally the exponents are biased, which means that for float it ranges from 2^(-127) to 2^(+ 127) and for double it ranges from 2^(-1024) to 2^(+1024). ~Himanshu Aggarwal On Tue, Apr 13, 2010 at 6:10 AM, Anil C R cr.a...@gmail.com wrote: correct me if I'm wrong but, float has a precision of around 8 digits. and double 16 digits... if you want arbitrary precision floating point numbers, try GNU BigNum library... Anil On Mon, Apr 12, 2010 at 9:54 PM, Himanshu Aggarwal lkml.himan...@gmail.com wrote: On Sun, Apr 11, 2010 at 6:55 PM, GentLeBoY vikrantsing...@gmail.comwrote: how to store fractional numbers with a fractional part having 25-30 digits after decimal place, does long double has the same precision as double?. 1 more prob. format specifier for long double is %lf and same for double, so if i write long double a; scanf(%lf,a); a=a*2; printf(%lf,a); why is the output -2. ? -- 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. Float has single precision. double has double precision. Long double has extended precision. For your requirement, even a float would suffice. check out the value of FLT_MAX . It is of the order of 10^37. ~Himanshu Aggarwal -- 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. -- Vikrant Singh -- Vikrant Singh -- 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
@rohit: For any given hash function , a worst case input can be designed to make all the keys get hashed to the same bucket [ hence counting the number of occurrences of an element wud take O(n*n/2) [ in both seperate chaining and Open addressing ). @all: majority voting algorithm suggested by navin naidu is very effcient and elegant. http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html . On Wed, Apr 14, 2010 at 10:20 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @rizwan : Think!!. *my algorithm is worst case O(n)*.. no doubt ! -- 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 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/http://web.iiit.ac.in/%7Eprakharjain/ On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar aryansmit3...@gmail.comwrote: 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 . 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. -- Thanks and regards Rizwan A Hudda http://sites.google.com/site/rizwanhudda -- 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
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
.
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 group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the mode in a set of integers
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...@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
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.
--
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
