[algogeeks] efficient backtracking algorithm for the coin changing problem
Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- 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] efficient backtracking algorithm for the coin changing problem
this is dynamic programming problem. try to use dynamic programming... On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- 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. -- 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.
Re: [algogeeks] efficient backtracking algorithm for the coin changing problem
y u need backtracking i think it can be done with DP On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- 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. -- How soon 'not now' becomes 'never'... -- 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] efficient backtracking algorithm for the coin changing problem
What do u mean by y u need backtracking DP needs backtracking to reconstruct the solution. -Rohit On Sat, Apr 10, 2010 at 3:27 PM, Ashish Mishra amishra@gmail.comwrote: y u need backtracking i think it can be done with DP On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- 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. -- How soon 'not now' becomes 'never'... -- 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] Finding all prime less than 10^8
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
attachment: My+Sign.JPG
Re: [algogeeks] efficient backtracking algorithm for the coin changing problem
here is simple way to do it..: A[1000] //1000 is maximum formadable sum can be provided.. S is set of coins that you have,K is the sum to be formed initialize the array A by larege value for(x in S): A[x]=1 for 0i1000 for 0j1000 if(i+j1000 A[i]+A[j]A[i+j] ) A[i+j]=A[i]+A[j] return A[K] On Sat, Apr 10, 2010 at 6:27 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: What do u mean by y u need backtracking DP needs backtracking to reconstruct the solution. -Rohit On Sat, Apr 10, 2010 at 3:27 PM, Ashish Mishra amishra@gmail.com wrote: y u need backtracking i think it can be done with DP On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- 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. -- How soon 'not now' becomes 'never'... -- 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. -- 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. -- 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.
[algogeeks] Complexity of searching in this alternate representation of tree
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] combination problem
It's equivalent to (x1-1)+(x2-1)+. . .+(xk-1)=n-k (You need n=k) yi = xi - 1, so for every 1=i=k, we have that yi is non-negative. Now think about it as having (n-1) objects in a row, and you need to choose k-1 which will be black and the other n-k will be white so, the number of solutions is equal to (n-1)C(k-1). 2010/4/9 GentLeBoY vikrantsing...@gmail.com no. of solutions to linear equation as x1+x2+x3+. . .+xk=n , all variables are positive natural numbers how is it (n-1)C(k-1) plz explain -- 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. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru -- 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: Complexity of searching in this alternate representation of tree
A binary search tree, nodes are ordered. So if you go to the left
subtree the data in all of the nodes is less than the data in current
node. Going to right subtree all the data will be greater than the
data in current node.
In short we need to define an order in that tree (how is the data
arranged if at all. Or else it could potentially be O(n) - the number
of nodes in the tree.)
On Apr 10, 11: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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Complexity of searching in this alternate representation of tree
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.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
why don't you remove all even numbers from consideration and add 2
explicitly. I think that would help.
--
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 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.
--
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
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. -- 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.comwrote: 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.comwrote: 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 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. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. 338.gif361.gif
Re: [algogeeks] Re: Implement a queue using a stack
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/~rohitfeb14 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/ 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 algogeeks@googlegroups.com . To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com . To unsubscribe from this group, send email to
Re: [algogeeks] First k smallest elements
I realised now that it can be done easily as : we can find the kth largest element in O(n) using Linear general selection algorithm - Median of Medians algorithm Well , can we do better than O(n log n ) in creating a BST from an array of size n ? -- 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 10:46 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: 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. -- 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.comwrote: 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.comwrote: 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 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. -- 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 algogeeks+unsubscr...@googlegroups.com. For more
