Re: [algogeeks] Finding all prime less than 10^8
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
My+Sign.JPG
Re: [algogeeks] First k smallest elements
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.comwrote: 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/~rohitfeb14 On Mon, Apr 12, 2010 at 8:18 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: 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/~rohitfeb14 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. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.com wrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.com wrote: there are better solution of O(n) are posted in the thread... [?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com . To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.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. -- 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
Re: [algogeeks] First k smallest elements
are yaar... i meant BST... i thought that was obvious ! sry if i confused you -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Apr 12, 2010 at 12:38 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: 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/~rohitfeb14 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/~rohitfeb14 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. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.com wrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.com wrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- 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 algogeeks@googlegroups.com . To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options,
Re: [algogeeks] First k smallest elements
On Mon, Apr 12, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: 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/~rohitfeb14 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/~rohitfeb14 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/~rohitfeb14 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. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.com wrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.com wrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- 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
Re: [algogeeks] First k smallest elements
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/~rohitfeb14 On Mon, Apr 12, 2010 at 1:16 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: 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/~rohitfeb14 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/~rohitfeb14 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/~rohitfeb14 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. Please prove the correctness of your algorithm with the time complexity -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.com wrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.com wrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3)
Re: [algogeeks] Re: Complexity of searching in this alternate representation of tree
@Himanshu.
from what i think the complexity would be log(n) but the base would be the
no. of siblings that the node has.
Check if this answer is correct.
On Sun, Apr 11, 2010 at 2:08 PM, Himanshu Aggarwal
lkml.himan...@gmail.comwrote:
@Dave n Harshi, thanks for your answer.
I am still not clear very much . May be u can help in elucidating your
replies.
If such a tree is degenerate, then the complexity of search is O(n), but if
it is a well-balanced tree, where some nodes may have 'k' children and some
nodes may have 'm' children , (where 'k' and 'm' are more than 2 and may not
be necessarily equal) , then what would be the comlexity of searching?
Would it of the order of log_2(n) or some other order like log_k(n) ? Or,
Is it that the base of the logarithm is not at all important here?
I hope I have made my doubt clear.
~Himanshu Aggarwal
On Sun, Apr 11, 2010 at 9:01 AM, Dave dave_and_da...@juno.com wrote:
Your statement about the complexity of searching a binary search tree
applies only if the tree is balanced. In a degenerate tree, e.g.,
where each node has only one son, so that the tree is essentialy a
linked list, the complexity of searching is O(n).
Dave
On Apr 10, 10:56 am, Himanshu Aggarwal lkml.himan...@gmail.com
wrote:
Hi,
The book on data structures by Langsam and Tanenbaum gives an alternate
representation of trees as :
struct treenode {
int data;
struct treenode * son;
struct treenode * sibling;
};
Such type of nodes can be used to make trees in which each node can have
any
number of siblings.
I am unable to understand the algorithmic complexity of searching for a
node
in such a tree?
While a simple binary search tree gives search complexity as log_2(n),
where
'n' are the number of nodes in the tree, does such a tree also gives
logarithmic complexity? In case it gives a logarithmic complexity, what
would be the base of logarithm in this case. Would it be 2 or some
number
'k' where 'k' might be dependent on certain factors?
Also, what might be the exact searching algo in this kind of a tree?
Some
pseudo code would be really appreciated.
Thanks for your help in understanding this problem.
With Regards,
Himanshu
--
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] First k smallest elements
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.comwrote: 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. Please prove the correctness of your algorithm with the time 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, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.com wrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So
Re: [algogeeks] First k smallest elements
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/~rohitfeb14 On Mon, Apr 12, 2010 at 3:20 PM, souri datta souri.isthe...@gmail.comwrote: 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. Please prove the correctness of your algorithm with the time 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, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk)
Re: [algogeeks] First k smallest elements
Oh yes.Median of medians selection algo is with the best complexity O(n). anythin else? On Mon, Apr 12, 2010 at 7:51 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: 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/~rohitfeb14 On Mon, Apr 12, 2010 at 3:20 PM, souri datta souri.isthe...@gmail.comwrote: 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. Please prove the correctness of your algorithm with the time 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, Mar 29, 2010 at 11:15 AM, blackDiamond patidarc...@gmail.com wrote: nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above
Re: [algogeeks] store fractional numbers with high precision
On Sun, Apr 11, 2010 at 6:55 PM, GentLeBoY vikrantsing...@gmail.com wrote: 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.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
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.comwrote: 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this
Re: [algogeeks] store fractional numbers with high precision
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.comwrote: 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
