[algogeeks] Implementation of Algorithms
I am new to the world of programming. I have to solve the problems on the spoj.pl , but I have no idea that how I would implement the algorithms in any programming language. Pls help me. I need a solution of this problem. Thanx scanfile -- 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]
Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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.
Re: [algogeeks]
With only this info and without preprocessing , you need to scan all the N integers in the list atleast once. Hence cannot be better than O(n). If preprocessing is allowed you can compute the answers for all n^2 pairs of x1,x2 and when some one asks , return the corresponding list. In that case it would be better that O(n). !! -Rohit On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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. -- 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]
is the list is sorted...or in some order... i feel unless the point in the list in some order eg: sorted, it will be difficult to get soluiton less than O(n) On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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.
Re: [algogeeks]
I guess she was asking that the per query complexity should be better that O(n). If that is the case then you can use any of these Simple RMQ O(sqrt(n)) Segment/Interval Trees O(lgn) Binary Indexed Trees O(lgn) On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: With only this info and without preprocessing , you need to scan all the N integers in the list atleast once. Hence cannot be better than O(n). If preprocessing is allowed you can compute the answers for all n^2 pairs of x1,x2 and when some one asks , return the corresponding list. In that case it would be better that O(n). !! -Rohit On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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. -- 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]
I think it can be done in logn time ( I assume the list is sorted, is there an order log n sorting algo, then i can even sort it in log n time ? ( I am new to algorithms ) ). 1. binary search for low=x1. 2. binary search for high=x2. both will take log n time. Print all values between them then in O(x2-x1) time. Is this correct? On Wed, Mar 31, 2010 at 12:58 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: With only this info and without preprocessing , you need to scan all the N integers in the list atleast once. Hence cannot be better than O(n). If preprocessing is allowed you can compute the answers for all n^2 pairs of x1,x2 and when some one asks , return the corresponding list. In that case it would be better that O(n). !! -Rohit On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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. -- 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]
ok...sorry u asked the data structure.. On Wed, Mar 31, 2010 at 11:54 AM, BlackdiamonD patidarc...@gmail.comwrote: is the list is sorted...or in some order... i feel unless the point in the list in some order eg: sorted, it will be difficult to get soluiton less than O(n) On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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 -- 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] Implementation of Algorithms
you can go through this.: http://www.topcoder.com/tc?d1=tutorialsd2=alg_indexmodule=Static and you can follow: Art of Uva online judge for getting started in this contest... On Wed, Mar 31, 2010 at 12:05 AM, scanfile rahul08k...@gmail.com wrote: I am new to the world of programming. I have to solve the problems on the spoj.pl , but I have no idea that how I would implement the algorithms in any programming language. Pls help me. I need a solution of this problem. Thanx scanfile -- 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.
Re: [algogeeks]
what if your sort the element.first time.. applying binary search on list for x1 (getting minimum index ) applying binary search on list for x2(getting maximum index) element between this index will be the answer. complexity:O(log(N)) for getting the range. (not considering the sorting) On Wed, Mar 31, 2010 at 11:55 AM, BlackdiamonD patidarc...@gmail.comwrote: ok...sorry u asked the data structure.. On Wed, Mar 31, 2010 at 11:54 AM, BlackdiamonD patidarc...@gmail.comwrote: is the list is sorted...or in some order... i feel unless the point in the list in some order eg: sorted, it will be difficult to get soluiton less than O(n) On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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 -- BL/\CK_D!AMOND -- 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]
What do you mean by points ? .. Are you referring to the integer values stored ? . 1.) If the question is, given N integers.. and given x1 and x2, report all integers x (x1=x=x2), you can't do better than O(N), as going through input itself takes O(N). . 2.) if the question is, given N integers and Q queries, each query is as ques1, then you may sort it initially and answer each query. It will be O( N log N ) + Q . O ( logN + (x2-x1) ). - AK On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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. -- Anil Kishore -- 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: how to convert a BST into a sorted doubly linked list.
Algorithm :
1 Do inorder traversal and at the time of reading data from tree, add
data to doubly link list.
(Inorder traversal will give you sorted order data and it can be
added to DLL. Thus, we can get sorted DLL.)
Code :
struct node
{
struct node *left;
int data;
struct node *right;
};
struct dllist {
int number;
struct dllist *next;
struct dllist *prev;
};
struct dllist *head, *tail, *listnode;
void bstToDLL(struct node *treenode) {
treeTraverse(treenode);
for(listnode = head; listnode != NULL; listnode = listnode-next) {
printf(%d\n, listnode-number);
}
}
void treeTraverse(struct node *treenode)
{
if(treenode!=NULL)
{
treeTraverse(treenode-left);
listnode = (struct dllist *)malloc(sizeof(struct dllist));
listnode-number = treenode-data;
appendToDoublyLinkList(listnode);
treeTraverse(treenode-right);
}
else
return;
}
void appendToDoublyLinkList(struct dllist *listnode) {
if(head == NULL) {
head = listnode;
listnode-prev = NULL;
}
else {
tail-next = listnode;
listnode-prev = tail;
}
tail = listnode;
listnode-next = NULL;
}
On Mar 28, 3:13 pm, Piyush Verma 114piy...@gmail.com wrote:
how to convert a BST into a sorted doubly linked list.
is there any solution of this question.
--
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] Implementation of Algorithms
First learn a language of your choice and then you can start solving over there On Wed, Mar 31, 2010 at 12:05 AM, scanfile rahul08k...@gmail.com wrote: I am new to the world of programming. I have to solve the problems on the spoj.pl , but I have no idea that how I would implement the algorithms in any programming language. Pls help me. I need a solution of this problem. Thanx scanfile -- 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] Implementation of Algorithms
Hii, what is Art of Uva online judge Does it contain some training material like USACO -- 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]
We can make a query tree and then each query will take O(log n+k) time. On Wed, Mar 31, 2010 at 12:48 PM, Anil Kishore anil.dai...@gmail.com wrote: What do you mean by points ? .. Are you referring to the integer values stored ? . 1.) If the question is, given N integers.. and given x1 and x2, report all integers x (x1=x=x2), you can't do better than O(N), as going through input itself takes O(N). . 2.) if the question is, given N integers and Q queries, each query is as ques1, then you may sort it initially and answer each query. It will be O( N log N ) + Q . O ( logN + (x2-x1) ). - AK On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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. -- Anil Kishore -- 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.
Re: [algogeeks] Implementation of Algorithms
How much time to u have? If you have got more than a month and u don't know any language; then I'll suggest you to learn a programming language like C++ or Java. In my opinion, C++ is the best language for these kind of problems :) Regards Umer. On Wed, Mar 31, 2010 at 5:12 PM, naga vinod kumar vinodkumark...@gmail.comwrote: Hii, what is Art of Uva online judge Does it contain some training material like USACO -- 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] Implementation of Algorithms
ok i previously i written wrong it is :*Art-of-Programming*-Contest-SE-for- *Uva book for basic of programming and some of the solving methods for problems. here is the Link Art_of_Programming_Contest_SE_for_uva.pdfhttp://online-judge.uva.es/p/Art_of_Programming_Contest_SE_for_uva.pdf * On Wed, Mar 31, 2010 at 5:42 PM, naga vinod kumar vinodkumark...@gmail.comwrote: Hii, what is Art of Uva online judge Does it contain some training material like USACO -- 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.
Re: [algogeeks] Re: how to convert a BST into a sorted doubly linked list.
@web-hav
*I think the actual problem is in place changing a bst into a DLL(Doubly
linked list) without using extra space .*
If you are allowed to use extra space then problem is pretty simple and your
code solves its purpose.
Shrish Chandra Mishra
CSE NIT,Allahabad
On Wed, Mar 31, 2010 at 3:38 PM, web-hav vaibhav...@gmail.com wrote:
Algorithm :
1 Do inorder traversal and at the time of reading data from tree, add
data to doubly link list.
(Inorder traversal will give you sorted order data and it can be
added to DLL. Thus, we can get sorted DLL.)
Code :
struct node
{
struct node *left;
int data;
struct node *right;
};
struct dllist {
int number;
struct dllist *next;
struct dllist *prev;
};
struct dllist *head, *tail, *listnode;
void bstToDLL(struct node *treenode) {
treeTraverse(treenode);
for(listnode = head; listnode != NULL; listnode = listnode-next) {
printf(%d\n, listnode-number);
}
}
void treeTraverse(struct node *treenode)
{
if(treenode!=NULL)
{
treeTraverse(treenode-left);
listnode = (struct dllist *)malloc(sizeof(struct dllist));
listnode-number = treenode-data;
appendToDoublyLinkList(listnode);
treeTraverse(treenode-right);
}
else
return;
}
void appendToDoublyLinkList(struct dllist *listnode) {
if(head == NULL) {
head = listnode;
listnode-prev = NULL;
}
else {
tail-next = listnode;
listnode-prev = tail;
}
tail = listnode;
listnode-next = NULL;
}
On Mar 28, 3:13 pm, Piyush Verma 114piy...@gmail.com wrote:
how to convert a BST into a sorted doubly linked list.
is there any solution of this question.
--
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]
The list of N integers is not sorted. The solution is asked for a particular query. @Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or *Segment Interval trees*. May be you opted for the correct data structure. Please give the algorithm. @All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in O(logn) will be less efficient than the simple solution of O(n). Think on the data structure that can optimize it. Is it possible in time complexity O(n)? -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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.
Re: [algogeeks]
@All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in O(logn) will be less efficient than the simple solution of O(n). Think on the data structure that can optimize it. Is it possible in time complexity O(n)? If you want to do the operation just once then it cannot be done faster than O(n) time. Even the mentioned data structures require atleast O(n) amount of preprocessing. All the mentioned algorithms are available here http://www.topcoder.com/tc?d1=tutorialsd2=alg_indexmodule=Static Hope it helps On Wed, Mar 31, 2010 at 8:26 PM, Priyanka Chatterjee dona.1...@gmail.comwrote: The list of N integers is not sorted. The solution is asked for a particular query. @Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or *Segment Interval trees*. May be you opted for the correct data structure. Please give the algorithm. @All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in O(logn) will be less efficient than the simple solution of O(n). Think on the data structure that can optimize it. Is it possible in time complexity O(n)? -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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. -- 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]
*Binary Indexed Trees* or *Segment Interval trees*. building them also it will take O(n log(n)) ..i feel for a particular query it will be difficult less than O(n) .because .u must know all the element. On Wed, Mar 31, 2010 at 8:26 PM, Priyanka Chatterjee dona.1...@gmail.comwrote: The list of N integers is not sorted. The solution is asked for a particular query. @Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or *Segment Interval trees*. May be you opted for the correct data structure. Please give the algorithm. @All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in O(logn) will be less efficient than the simple solution of O(n). Think on the data structure that can optimize it. Is it possible in time complexity O(n)? -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.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.
