[algogeeks] square root problem
1 can anyone tell me the algo used by below problem provide which is the best algo to compute square root of number.?? 2. can any one provide the solution of converting no. from base b1 to b2 without using intermediate base. #includestdio.h #includeconio.h int main() { float a,b,e=0.1,p,k; //clrscr(); //textcolor(GREEN); do { printf( ÛÛÛ); printf(xDB PROGRAM TO FIND SQUARE ROOT OF A NUMBERxDB); printf( ÛÛÛ); printf(ENTER A NUMBER(-1 to Quit) :); scanf(%f,k); a=k;p=a*a; while(p-k=e) { b=(a+(k/a))/2; a=b; p=a*a; } printf(SQUARE ROOT IS = %f,a); getch(); //clrscr(); }while(k!=-1); getch(); } -- 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] Cube Root of a binary number
Cab somebody suggest an algorithm to find the cube root of a number? -- 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] Cube root of a number
Can somebody suggest an efficient algorithm to find the cube root of a number? -- 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] Brent's algorithm
@Nikhil : Thanks a lot. On Wed, Aug 18, 2010 at 10:32 AM, jaladhi dave jaladhi.k.d...@gmail.com wrote: Check out this link http://en.wikipedia.org/wiki/Cycle_detection On Wed, Aug 18, 2010 at 5:12 AM, jayapriya surendran priya7...@gmail.com wrote: hi..i wanna know what is brent's algorithm n whether it can be used to detect loops in linked list.If yes..is it better than Floyd's cycle finding algo? -- 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. -- 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] Array Problem
On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} There is an obvious check. N1==N2 at the beginning. On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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] linked list
wats d problem in my display() #includeiostream #includemalloc.h #include string.h using namespace std; struct node { char *name; struct node *next; }; typedef struct node Node; void createList(Node **head ) { char str[20]; char *p; coutEnter a String: ; gets (str) ; p = str; if((strlen(p))2) return; Node *temp=*head; Node *newnode=(Node*)malloc(sizeof(Node)); newnode-name=p; newnode-next=NULL; if(!temp) *head = newnode; else { while(temp-next) temp = temp-next; temp-next = newnode; } createList(head); } void display(Node *head) { cout\n; for( ; head ; head=head-next) cout\thead-name; cout\n; } int main() { Node *head=NULL; while(1) { cout\n\t\tMENU\n; cout0 : To exit.\n; cout1 : To create a linear link list.\n; cout2 : To display the list.\n; char choice; choice = getchar(); getchar(); if(choice=='0') break; switch(choice) { case '1': createList(head ); break; case '2': display(head); break; default: coutEnter valid choice.; } } system(pause); return 0; } -- 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: Linked List
you are right in the way in cpp code it is not required but in C , you can not write like node * start. it only recognise new type when typedef is applied. second one is already explained by vijay On Aug 18, 6:16 pm, Vijay kvija...@gmail.com wrote: 1. typedef is used to rename the data type. Here struct node is actual data type of linked list node and is renamed to NODE using typedef .Instead of using struct node each time we declares a new node variable we can use simply NODE. 2.**start is required if you pass actual parameter as address, suppose NODE *temp = (NODE *) malloc (sizeof(NODE)); is the new node created; and you have to use the following function call createemptylist(temp); It is important to pass this by address as changes made in the called function should be reflected on the linked list. -- 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] Array Problem
How about combining sum and multiplication in the first step. As in perform both sum and multiplication or may be sum of squares. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.comwrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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] Cube root of a number
use newton raphson method On Thu, Aug 19, 2010 at 2:36 AM, asdfghjk georgymk...@gmail.com wrote: Can somebody suggest an efficient algorithm to find the cube root of a number? -- 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. -- regards Apoorve Mohan -- 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] linked list
make declaration of char str[20] to char *str=(char*)malloc(20*sizeof(char)); and it will work . On Wed, Aug 18, 2010 at 11:23 PM, Raj Jagvanshi raj.jagvan...@gmail.comwrote: wats d problem in my display() #includeiostream #includemalloc.h #include string.h using namespace std; struct node { char *name; struct node *next; }; typedef struct node Node; void createList(Node **head ) { char str[20]; char *p; coutEnter a String: ; gets (str) ; p = str; if((strlen(p))2) return; Node *temp=*head; Node *newnode=(Node*)malloc(sizeof(Node)); newnode-name=p; newnode-next=NULL; if(!temp) *head = newnode; else { while(temp-next) temp = temp-next; temp-next = newnode; } createList(head); } void display(Node *head) { cout\n; for( ; head ; head=head-next) cout\thead-name; cout\n; } int main() { Node *head=NULL; while(1) { cout\n\t\tMENU\n; cout0 : To exit.\n; cout1 : To create a linear link list.\n; cout2 : To display the list.\n; char choice; choice = getchar(); getchar(); if(choice=='0') break; switch(choice) { case '1': createList(head ); break; case '2': display(head); break; default: coutEnter valid choice.; } } system(pause); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Ram Narayan Das mob: +91 9177711195 -- 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] Permutation of Array.
An interesting idea would be treat the inputs as strings and sort them. On Thu, Aug 19, 2010 at 4:01 AM, amit amitjaspal...@gmail.com wrote: Given an array of numbers. Calculate a permutation when the concatenate number is smallest. For instance, [55,31,312,33] is 312313355 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Data Structure for URL matching
Hi Amit, are you some sort of a genius or what do I expect now!? Can you answer my question? Best regards, On Aug 17, 12:24 am, Amit Jaspal amitjaspal...@gmail.com wrote: http://www.ahhf45.com/info/Data_Structures_and_Algorithms/resources/t... Refer this link. On Mon, Aug 16, 2010 at 10:29 PM, Chi c...@linuxdna.com wrote: I'm not sure what you want. I have post a solution to search for wildcards in tries. Now you claim to do it better with TS-Trees. Do you know who to compute a reverse TS-Tree? And why don't you try first to code a radix-tree, which is a compressed trie and build then the reverse radix-tree? Here is a solution to code a radix-tree, crit-bit- tree, pat-tree with mininmal understanding of comupter science: http://www.codeproject.com/KB/string/pat_and_huff.aspx IMHO I'm not sure why a Ternary-Search-Tree should be faster then a Radix-Tree? If a radix tree is already a binary-tree version of the trie, then can you explain me the advantage of a ternary-search-tree? On Aug 15, 8:31 pm, Amit Jaspal amitjaspal...@gmail.com wrote: Seems a gud idea . I have read we can do better with Ternary Search Trees .Can anybody has any idea about it? On Sun, Aug 15, 2010 at 11:44 PM, Chi c...@linuxdna.com wrote: What you may need is a reverse trie. You may take a look at this: http://phpir.com/tries-and-wildcards On Aug 15, 3:21 pm, amit amitjaspal...@gmail.com wrote: In our indexes, we have millions of URLs each of which has a link to some page contents, that is, URL-contents. Now, suppose a user types a query with wild cards *, which represent 0 or multiple occurrences of any characters, how do you build the indexes such that such a type of query can be executed efficiently by finding all corresponding URLs-contents efficiently. For example, given a queryhttp://www.*o*ve* ou.com. You need to find iloveyou.com, itveabcu.com, etc. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email toalgoge...@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. -- Amit Jaspal Btech IT IIIT- Allahabad -- 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. -- Amit Jaspal Btech IT IIIT- Allahabad -- 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] linked list
void display(Node *head) { cout\n; for( ; head ; head=head-next) cout\thead-name; cout\n; } when head reaches last node condition head is true , then head will become head-next which is null , and it will try to print the name field from of a null value which is error On Wed, Aug 18, 2010 at 10:53 PM, Raj Jagvanshi raj.jagvan...@gmail.comwrote: wats d problem in my display() #includeiostream #includemalloc.h #include string.h using namespace std; struct node { char *name; struct node *next; }; typedef struct node Node; void createList(Node **head ) { char str[20]; char *p; coutEnter a String: ; gets (str) ; p = str; if((strlen(p))2) return; Node *temp=*head; Node *newnode=(Node*)malloc(sizeof(Node)); newnode-name=p; newnode-next=NULL; if(!temp) *head = newnode; else { while(temp-next) temp = temp-next; temp-next = newnode; } createList(head); } void display(Node *head) { cout\n; for( ; head ; head=head-next) cout\thead-name; cout\n; } int main() { Node *head=NULL; while(1) { cout\n\t\tMENU\n; cout0 : To exit.\n; cout1 : To create a linear link list.\n; cout2 : To display the list.\n; char choice; choice = getchar(); getchar(); if(choice=='0') break; switch(choice) { case '1': createList(head ); break; case '2': display(head); break; default: coutEnter valid choice.; } } system(pause); return 0; } -- 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] Adobe Questions
1. Suppose a class A is given as : class A { public : void print() { coutHello; } } int main() { A * a; A* b = NULL; a-print(); b-print(); } What is the output? 2. Given an array containing 0,1,2 in any order. Sort the array in a single pass. 3. Write a code to implement spiral traversal of the BST. 4. Given a string containing the binary representation of a number. Write a code to find the 2s complement of the number. -- 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] 0's and 1's yet again!!!
Hi Amit Am I allowed to keep counters to count the number of 1's and 0s right? The condition of not using extra memory is for the array!? Regards Ashutosh 2010/8/18 amit amitjaspal...@gmail.com you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- 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] linked list
no it head to head-next at the end of for loop block not at the beginning. try out this for (int t=0;t5;t++) cout\nt; On Thu, Aug 19, 2010 at 5:22 PM, vineeth mohan vm.vineethmo...@gmail.comwrote: void display(Node *head) { cout\n; for( ; head ; head=head-next) cout\thead-name; cout\n; } when head reaches last node condition head is true , then head will become head-next which is null , and it will try to print the name field from of a null value which is error On Wed, Aug 18, 2010 at 10:53 PM, Raj Jagvanshi raj.jagvan...@gmail.comwrote: wats d problem in my display() #includeiostream #includemalloc.h #include string.h using namespace std; struct node { char *name; struct node *next; }; typedef struct node Node; void createList(Node **head ) { char str[20]; char *p; coutEnter a String: ; gets (str) ; p = str; if((strlen(p))2) return; Node *temp=*head; Node *newnode=(Node*)malloc(sizeof(Node)); newnode-name=p; newnode-next=NULL; if(!temp) *head = newnode; else { while(temp-next) temp = temp-next; temp-next = newnode; } createList(head); } void display(Node *head) { cout\n; for( ; head ; head=head-next) cout\thead-name; cout\n; } int main() { Node *head=NULL; while(1) { cout\n\t\tMENU\n; cout0 : To exit.\n; cout1 : To create a linear link list.\n; cout2 : To display the list.\n; char choice; choice = getchar(); getchar(); if(choice=='0') break; switch(choice) { case '1': createList(head ); break; case '2': display(head); break; default: coutEnter valid choice.; } } system(pause); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Ram Narayan Das mob: +91 9177711195 -- 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] 0's and 1's yet again!!!
void ArrayShifting(int *str, int size) { int odd=1, even=0; while(odd size) { int position; if(str[even]!=0) { position = even+1; while(position size) { if(str[position]==0) { str[position]=1;str[even]=0;break;} position = position+2; } } even = even+2; if(str[odd]!=1) { position = odd+1; while(position size) { if(str[k]==0) { str[position]=0;str[odd]=1;break;} position = position+2; } } odd=odd+2; } } This code seems working for me, If you agree then we can work on measuring the complexity improving the code accordingly. On Thu, Aug 19, 2010 at 5:27 PM, Ashutosh Tamhankar asshuto...@gmail.comwrote: Hi Amit Am I allowed to keep counters to count the number of 1's and 0s right? The condition of not using extra memory is for the array!? Regards Ashutosh 2010/8/18 amit amitjaspal...@gmail.com you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Enumerate restricted knight walks
Find the number of ways a knight can move from top left square to bottom right square in an M*N Chess board with only the following moves allowed: a) 1 square right ; 2 squares down b) 1 square right ; 2 squares up and b) 2 squares right ; 1 square down. -- 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: square root problem
The square root algorithm is using Newton's Method. The particular case for square root sometimes is called Heron's Method. Recall that Newton's Method is an iterative algorithm that improves a guess at the zero of a function. Given f(x), to find the zero of f, start with a point x_1 sufficiently close to the zero and iterate as follows: x_{i+1} = x_i - f(x_i) / f'(x_i), where f' is the derivative of f. In the case of finding the square root of k, let f(x) = x^2 - k. Then the zero of f occurs when x = sqrt(k). f'(x) = 2x. So Newton's Method is x_{i+1} = x_i - (x_i^2 - k) / (2x_i) which simplifies to x_{i+1} = (x_i + k / x_i) / 2 which is what is programmed in your code. Dave On Aug 19, 1:56 am, bittu shashank7andr...@gmail.com wrote: 1 can anyone tell me the algo used by below problem provide which is the best algo to compute square root of number.?? 2. can any one provide the solution of converting no. from base b1 to b2 without using intermediate base. #includestdio.h #includeconio.h int main() { float a,b,e=0.1,p,k; //clrscr(); //textcolor(GREEN); do { printf( ÛÛÛ); printf( xDB PROGRAM TO FIND SQUARE ROOT OF A NUMBERxDB); printf( ÛÛÛ); printf(ENTER A NUMBER(-1 to Quit) :); scanf(%f,k); a=k;p=a*a; while(p-k=e) { b=(a+(k/a))/2; a=b; p=a*a; } printf(SQUARE ROOT IS = %f,a); getch(); //clrscr(); }while(k!=-1); getch(); } -- 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] 0's and 1's yet again!!!
shiftZeroOne(int *arr,int size) { int odd=1,even=0; while(odd = size even =size) { if ( arr[even] != 1 ) even+=2; if ( arr[odd] != 0 ) odd+=2; if ( arr[even] == 1 arr[odd] == 0 ) { arr[even]=0; arr[odd]=1; } } } On Thu, Aug 19, 2010 at 5:53 PM, Rais Khan raiskhan.i...@gmail.com wrote: void ArrayShifting(int *str, int size) { int odd=1, even=0; while(odd size) { int position; if(str[even]!=0) { position = even+1; while(position size) { if(str[position]==0) { str[position]=1;str[even]=0;break;} position = position+2; } } even = even+2; if(str[odd]!=1) { position = odd+1; while(position size) { if(str[k]==0) { str[position]=0;str[odd]=1;break;} position = position+2; } } odd=odd+2; } } This code seems working for me, If you agree then we can work on measuring the complexity improving the code accordingly. On Thu, Aug 19, 2010 at 5:27 PM, Ashutosh Tamhankar asshuto...@gmail.comwrote: Hi Amit Am I allowed to keep counters to count the number of 1's and 0s right? The condition of not using extra memory is for the array!? Regards Ashutosh 2010/8/18 amit amitjaspal...@gmail.com you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Ram Narayan Das mob: +91 9177711195 -- 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] 0's and 1's yet again!!!
{ int odd=1,even=0; while(odd = size even =size) { if ( arr[even] != 1 ) even+=2; if ( arr[odd] != 0 ) odd+=2; if ( arr[even] == 1 arr[odd] == 0 ) { arr[even]=0; arr[odd]=1; } } } On Thu, Aug 19, 2010 at 7:00 PM, ram das ramnaraya...@gmail.com wrote: shiftZeroOne(int *arr,int size) { int odd=1,even=0; while(odd = size even =size) { if ( arr[even] != 1 ) even+=2; if ( arr[odd] != 0 ) odd+=2; if ( arr[even] == 1 arr[odd] == 0 ) { arr[even]=0; arr[odd]=1; } } } On Thu, Aug 19, 2010 at 5:53 PM, Rais Khan raiskhan.i...@gmail.comwrote: void ArrayShifting(int *str, int size) { int odd=1, even=0; while(odd size) { int position; if(str[even]!=0) { position = even+1; while(position size) { if(str[position]==0) { str[position]=1;str[even]=0;break;} position = position+2; } } even = even+2; if(str[odd]!=1) { position = odd+1; while(position size) { if(str[k]==0) { str[position]=0;str[odd]=1;break;} position = position+2; } } odd=odd+2; } } This code seems working for me, If you agree then we can work on measuring the complexity improving the code accordingly. On Thu, Aug 19, 2010 at 5:27 PM, Ashutosh Tamhankar asshuto...@gmail.com wrote: Hi Amit Am I allowed to keep counters to count the number of 1's and 0s right? The condition of not using extra memory is for the array!? Regards Ashutosh 2010/8/18 amit amitjaspal...@gmail.com you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Ram Narayan Das mob: +91 9177711195 -- Thanks Regards Ram Narayan Das mob: +91 9177711195 -- 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: Array Problem
@Nikhil: A = {0,2,2}, B = {0,0,4}. Rather than challenging everyone to keep coming up with counterexamples, please provide a rationale as to why an algorithm such as this should work. It looks as if you have two equations in 2N unknowns and are trying to assert that the only solution is A_1 = B_1, A_2 = B_2, etc. (where I have assumed that each array is sorted). Dave On Aug 19, 2:24 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i];} if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hidequoted text - - Show quoted text -- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd- Hide quoted text - -
Re: [algogeeks] 0's and 1's yet again!!!
@ Ram Thats a cool version. I shall work on improving my version below. Does anybody see any flaws in the algorithm? Summary: It starts looking at the array from the head and tails at tandem. It does a single pass through the array swapping elements from head to tail upon finding an appropriate element at the tail by going down the tail. Regards Ashutosh Pseudo code of the algorithm head = 0; tail = sizeOfArray; zeros = 0; ones = 0; for (head = 0; head sizeOfArray; head++) { if head is odd { if array[head] is 0 { zeros = zeros + 1 if tail = head; tail = tail +1 while array[tail] is 0 { tail = tail - 1 zeros = zeros +1 } // tail is one swap array[tail] array[head] ones = ones +1 // continue looping } else // array head is 1 { // continue looping if ones + zeros = sizeOfArray { if ones zeroesimbalance = 1 exit // done or error occurred. } } } else// position is even { if array[head] is 1 { ones = ones +1 if tail = head; tail = tail +1 while array[tail] is 1 { tail = tail - 1 ones = ones +1 } // tail is zero zeros = zeros +1 swap array[tail] - array[head] //continue looping } else // array head is 0 { //continue looping; if ones + zeros = sizeOfArray { if ones zeroesimbalance = 1 exit // done or error occurred. } } } } 2010/8/19 ram das ramnaraya...@gmail.com { int odd=1,even=0; while(odd = size even =size) { if ( arr[even] != 1 ) even+=2; if ( arr[odd] != 0 ) odd+=2; if ( arr[even] == 1 arr[odd] == 0 ) { arr[even]=0; arr[odd]=1; } } } On Thu, Aug 19, 2010 at 7:00 PM, ram das ramnaraya...@gmail.com wrote: shiftZeroOne(int *arr,int size) { int odd=1,even=0; while(odd = size even =size) { if ( arr[even] != 1 ) even+=2; if ( arr[odd] != 0 ) odd+=2; if ( arr[even] == 1 arr[odd] == 0 ) { arr[even]=0; arr[odd]=1; } } } On Thu, Aug 19, 2010 at 5:53 PM, Rais Khan raiskhan.i...@gmail.comwrote: void ArrayShifting(int *str, int size) { int odd=1, even=0; while(odd size) { int position; if(str[even]!=0) { position = even+1; while(position size) { if(str[position]==0) { str[position]=1;str[even]=0;break;} position = position+2; } } even = even+2; if(str[odd]!=1) { position = odd+1; while(position size) { if(str[k]==0) { str[position]=0;str[odd]=1;break;} position = position+2; } } odd=odd+2; } } This code seems working for me, If you agree then we can work on measuring the complexity improving the code accordingly. On Thu, Aug 19, 2010 at 5:27 PM, Ashutosh Tamhankar asshuto...@gmail.com wrote: Hi Amit Am I allowed to keep counters to count the number of 1's and 0s right? The condition of not using extra memory is for the array!? Regards Ashutosh 2010/8/18 amit amitjaspal...@gmail.com you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- 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
[algogeeks] Re: 0's and 1's yet again!!!
It seems easy enough to put all of the zeros in the even positions and all of the ones in the odd positions in one pass. The difficulty is posed by the second condition, that if the number of zeros and ones is not equal, then leave everything alone. This seems to require two passes, either to determine if the number of zeros equals the number of ones, and then to store them as required, or to store them as required in the first pass and then restore them if if turns out that the number of zeros does not equal the number of ones. I.e., the one- pass combined with keeping them untouched is what makes this difficult. Dave On Aug 18, 3:24 pm, amit amitjaspal...@gmail.com wrote: you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- 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: 0's and 1's yet again!!!
Dave, check my pseudo code. Both the tasks of checking if the number of 1s and 0s is equal and sorting the array seems to to work in a single pass. 2010/8/19 Dave dave_and_da...@juno.com It seems easy enough to put all of the zeros in the even positions and all of the ones in the odd positions in one pass. The difficulty is posed by the second condition, that if the number of zeros and ones is not equal, then leave everything alone. This seems to require two passes, either to determine if the number of zeros equals the number of ones, and then to store them as required, or to store them as required in the first pass and then restore them if if turns out that the number of zeros does not equal the number of ones. I.e., the one- pass combined with keeping them untouched is what makes this difficult. Dave On Aug 18, 3:24 pm, amit amitjaspal...@gmail.com wrote: you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- 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] Longest Palindromic Substring
Hi All, Givan a string, you have to find the longest palindromic substring. For ex: Longest Palindromic substring for abclevelabc is level. What is the most optimised solution possible? Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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] 0's and 1's yet again!!!
Keeping counter will force you to make another PASS of the array which you cant do i suppose. On Thu, Aug 19, 2010 at 5:27 PM, Ashutosh Tamhankar asshuto...@gmail.comwrote: Hi Amit Am I allowed to keep counters to count the number of 1's and 0s right? The condition of not using extra memory is for the array!? Regards Ashutosh 2010/8/18 amit amitjaspal...@gmail.com you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- 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. -- Amit Jaspal Btech IT IIIT- Allahabad -- 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: Array Problem
Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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] Permutation of Array.
The critical thing here is how to define your comparator function to be used for sorting. Sorting using the normal comparator function will return the following: 31 33 55 312 Using insertion sort O(n^2) such that the resultant concatenation is smallest, should do it. The steps for [55,31,312,33] would be: 55 31 55 312 31 55 312 31 33 55 which gives the correct result :) Defining the comparator function on these lines should do it in O(nlogn) as well. On Thu, Aug 19, 2010 at 5:02 PM, Shiv ... shivsinha2...@gmail.com wrote: An interesting idea would be treat the inputs as strings and sort them. On Thu, Aug 19, 2010 at 4:01 AM, amit amitjaspal...@gmail.com wrote: Given an array of numbers. Calculate a permutation when the concatenate number is smallest. For instance, [55,31,312,33] is 312313355 -- 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. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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] 0's and 1's yet again!!!
@ram: This doesnt work for: arr[] = {1,0,0,0} Here, then number of 1's and 0's are not same. So the array should be left untouched. On Thu, Aug 19, 2010 at 7:02 PM, ram das ramnaraya...@gmail.com wrote: { int odd=1,even=0; while(odd = size even =size) { if ( arr[even] != 1 ) even+=2; if ( arr[odd] != 0 ) odd+=2; if ( arr[even] == 1 arr[odd] == 0 ) { arr[even]=0; arr[odd]=1; } } } On Thu, Aug 19, 2010 at 7:00 PM, ram das ramnaraya...@gmail.com wrote: shiftZeroOne(int *arr,int size) { int odd=1,even=0; while(odd = size even =size) { if ( arr[even] != 1 ) even+=2; if ( arr[odd] != 0 ) odd+=2; if ( arr[even] == 1 arr[odd] == 0 ) { arr[even]=0; arr[odd]=1; } } } On Thu, Aug 19, 2010 at 5:53 PM, Rais Khan raiskhan.i...@gmail.comwrote: void ArrayShifting(int *str, int size) { int odd=1, even=0; while(odd size) { int position; if(str[even]!=0) { position = even+1; while(position size) { if(str[position]==0) { str[position]=1;str[even]=0;break;} position = position+2; } } even = even+2; if(str[odd]!=1) { position = odd+1; while(position size) { if(str[k]==0) { str[position]=0;str[odd]=1;break;} position = position+2; } } odd=odd+2; } } This code seems working for me, If you agree then we can work on measuring the complexity improving the code accordingly. On Thu, Aug 19, 2010 at 5:27 PM, Ashutosh Tamhankar asshuto...@gmail.com wrote: Hi Amit Am I allowed to keep counters to count the number of 1's and 0s right? The condition of not using extra memory is for the array!? Regards Ashutosh 2010/8/18 amit amitjaspal...@gmail.com you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Ram Narayan Das mob: +91 9177711195 -- Thanks Regards Ram Narayan Das mob: +91 9177711195 -- 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. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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: Array Problem
@Nikhil Jindal: What you say is true for 2 numbers, but not for more than 2. 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36. Dave On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hidequoted text - - Show quoted text -- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology,
[algogeeks] Re: Longest Palindromic Substring
Isn't the longest palindromic substring is alevela??? On Aug 19, 7:16 pm, Nikhil Jindal fundoon...@yahoo.co.in wrote: Hi All, Givan a string, you have to find the longest palindromic substring. For ex: Longest Palindromic substring for abclevelabc is level. What is the most optimised solution possible? Please access the attached hyperlink for an important electronic communications disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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: Array Problem
1. Add sum of squares of all numbers in respective groups, if equal goto step 2. 2. XOR all elements of both groups, (if==0) elements are same. On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote: @Nikhil Jindal: What you say is true for 2 numbers, but not for more than 2. 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36. Dave On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hidequotedtext - - Show quoted text -- Hide quoted text - - Show quoted text - -- 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
Re: [algogeeks] Re: Longest Palindromic Substring
A substring is continuous, whereas a subsequence is discontinuous. alevela is a palindromic subsequence, and not a substring. On Thu, Aug 19, 2010 at 11:45 AM, Saikat Debnath saikat@gmail.comwrote: Isn't the longest palindromic substring is alevela??? On Aug 19, 7:16 pm, Nikhil Jindal fundoon...@yahoo.co.in wrote: Hi All, Givan a string, you have to find the longest palindromic substring. For ex: Longest Palindromic substring for abclevelabc is level. What is the most optimised solution possible? Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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] Permutation of Array.
Another method - 1. Group the numbers according to the number of digits (maybe hash buckets) 2. Sort in ascending order within each bucket (any efficient sorting algo) 3. Concatenate them by descending order of number of digits, and ascending order within the group. On Thu, Aug 19, 2010 at 7:37 AM, Nikhil Jindal fundoon...@yahoo.co.inwrote: The critical thing here is how to define your comparator function to be used for sorting. Sorting using the normal comparator function will return the following: 31 33 55 312 Using insertion sort O(n^2) such that the resultant concatenation is smallest, should do it. The steps for [55,31,312,33] would be: 55 31 55 312 31 55 312 31 33 55 which gives the correct result :) Defining the comparator function on these lines should do it in O(nlogn) as well. On Thu, Aug 19, 2010 at 5:02 PM, Shiv ... shivsinha2...@gmail.com wrote: An interesting idea would be treat the inputs as strings and sort them. On Thu, Aug 19, 2010 at 4:01 AM, amit amitjaspal...@gmail.com wrote: Given an array of numbers. Calculate a permutation when the concatenate number is smallest. For instance, [55,31,312,33] is 312313355 -- 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. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] best known transitive closure algorithm for graph
Hi all, In terms of runtime, what is the best known transitive closure algorithm for directed graphs? I am currently using Warshall's algorithm but its O(n^3). Although, due to the graph representation my implementation does slightly better (instead of checking all edges, it only checks all out going edges). Is there any transitive closure algorithm which is better than this? In particular, is there anything specifically for shared memory multi-threaded architectures? Thanks in advance. Raghava. PS: I posted this question at http://stackoverflow.com/questions/3517524/best-known-transitive-closure-algorithm-for-graph. Reposting it here, so that I may get more responses. -- 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] Permutation of Array.
@Divya : Does the algo you gave work for the set { 6,5,9,111} ? I hope it doesnt... Correct me if i am wrong -- 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] best known transitive closure algorithm for graph
Hi all, In terms of runtime, what is the best known transitive closure algorithm for directed graphs? I am currently using Warshall's algorithm but its O(n^3). Although, due to the graph representation my implementation does slightly better (instead of checking all edges, it only checks all out going edges). Is there any transitive closure algorithm which is better than this? In particular, is there anything specifically for shared memory multi- threaded architectures? Thanks in advance. Raghava. PS: I posted this question at http://stackoverflow.com/questions/3517524/best-known-transitive-closure-algorithm-for-graph. Reposting it here, so that I may get more responses. I deleted my earlier post to this group because it came in as a reply to a different post. -- 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] Permutation of Array.
By the algo I gave : 1. Grouping - 3 digits - 111 1 digit - 6,5,9 2. Sorting within each bucket 3 digits - 111 1 digit - 5,6,9 3. Concatenation by descending order of number of digits, and increasing order within each digit bucket - Grouping would then be - 3 digit numbers in sorted order followed by 1 digit numbers in sorted order 111 5 6 9 Is there a number smaller than 111569 that can be formed with the set given? Also, I am not sure about the complexity of this algo. On Thu, Aug 19, 2010 at 1:56 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Divya : Does the algo you gave work for the set { 6,5,9,111} ? I hope it doesnt... Correct me if i am wrong -- 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] Permutation of Array.
Never mind. This algo doesn't work properly. Apologies. On Thu, Aug 19, 2010 at 3:34 PM, Divya Chandrasekar divyac1...@gmail.comwrote: By the algo I gave : 1. Grouping - 3 digits - 111 1 digit - 6,5,9 2. Sorting within each bucket 3 digits - 111 1 digit - 5,6,9 3. Concatenation by descending order of number of digits, and increasing order within each digit bucket - Grouping would then be - 3 digit numbers in sorted order followed by 1 digit numbers in sorted order 111 5 6 9 Is there a number smaller than 111569 that can be formed with the set given? Also, I am not sure about the complexity of this algo. On Thu, Aug 19, 2010 at 1:56 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Divya : Does the algo you gave work for the set { 6,5,9,111} ? I hope it doesnt... Correct me if i am wrong -- 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] Permutation of Array.
@Divya chandrasekhar your algorithm doesn't satisfy the condition like {130,11} we can give so many examples like this so the solution may come like this follow these rules: 1.imagine that all the numbers are equal length.(i.e;if the numbers are not equal lenth just add 0's at right hand side to the numbers which have less number of digits) 2.now arrange all these numbers in ascending order. 3.now remove the additionally added zero numbers from the numbers to get original numbers soon i wiil write the code On Fri, Aug 20, 2010 at 2:34 AM, Divya Chandrasekar divyac1...@gmail.comwrote: Never mind. This algo doesn't work properly. Apologies. On Thu, Aug 19, 2010 at 3:34 PM, Divya Chandrasekar divyac1...@gmail.comwrote: By the algo I gave : 1. Grouping - 3 digits - 111 1 digit - 6,5,9 2. Sorting within each bucket 3 digits - 111 1 digit - 5,6,9 3. Concatenation by descending order of number of digits, and increasing order within each digit bucket - Grouping would then be - 3 digit numbers in sorted order followed by 1 digit numbers in sorted order 111 5 6 9 Is there a number smaller than 111569 that can be formed with the set given? Also, I am not sure about the complexity of this algo. On Thu, Aug 19, 2010 at 1:56 PM, BALARUKESH SIVARAMAN sbalarukesh1...@gmail.com wrote: @Divya : Does the algo you gave work for the set { 6,5,9,111} ? I hope it doesnt... Correct me if i am wrong -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
@Saikat: Rather than challenging everyone to keep coming up with counterexamples, please provide a rationale as to why an algorithm such as this should work. It looks as if you have two equations in 2N unknowns and are trying to assert that the only solution is A_1 = B_1, A_2 = B_2, etc. (where I have assumed that each array is sorted). Usually, it takes 2N equations to determine 2N unknowns, although other information about the solutions can lessen that number in certain circumstances. At least if you are going to propose something, do so only after you have tested it on all of the combinations of up to four numbers between -5 and 5. Dave On Aug 19, 11:52 am, Saikat Debnath saikat@gmail.com wrote: 1. Add sum of squares of all numbers in respective groups, if equal goto step 2. 2. XOR all elements of both groups, (if==0) elements are same. On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote: @Nikhil Jindal: What you say is true for 2 numbers, but not for more than 2. 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36. Dave On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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] Re: 0's and 1's yet again!!!
@Rais: I don't see that it leaves the array unchanged if the number of zeros does not equal the number of ones. Dave On Aug 19, 7:23 am, Rais Khan raiskhan.i...@gmail.com wrote: void ArrayShifting(int *str, int size) { int odd=1, even=0; while(odd size) { int position; if(str[even]!=0) { position = even+1; while(position size) { if(str[position]==0) { str[position]=1;str[even]=0;break;} position = position+2; } } even = even+2; if(str[odd]!=1) { position = odd+1; while(position size) { if(str[k]==0) { str[position]=0;str[odd]=1;break;} position = position+2; } } odd=odd+2; } } This code seems working for me, If you agree then we can work on measuring the complexity improving the code accordingly. On Thu, Aug 19, 2010 at 5:27 PM, Ashutosh Tamhankar asshuto...@gmail.comwrote: Hi Amit Am I allowed to keep counters to count the number of 1's and 0s right? The condition of not using extra memory is for the array!? Regards Ashutosh 2010/8/18 amit amitjaspal...@gmail.com you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY. -- 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.- Hide quoted text - - Show quoted text - -- 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: best known transitive closure algorithm for graph
You've done a similar thing. You've changed the current topic of this post. You need to start a new post/thread. On Aug 19, 11:59 am, Raghava vijaya_raghav...@yahoo.com wrote: Hi all, In terms of runtime, what is the best known transitive closure algorithm for directed graphs? I am currently using Warshall's algorithm but its O(n^3). Although, due to the graph representation my implementation does slightly better (instead of checking all edges, it only checks all out going edges). Is there any transitive closure algorithm which is better than this? In particular, is there anything specifically for shared memory multi- threaded architectures? Thanks in advance. Raghava. PS: I posted this question athttp://stackoverflow.com/questions/3517524/best-known-transitive-clos Reposting it here, so that I may get more responses. I deleted my earlier post to this group because it came in as a reply to a different post. -- 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] linked list
my display function print garbage value from begining On Thu, Aug 19, 2010 at 4:23 PM, ram das ramnaraya...@gmail.com wrote: make declaration of char str[20] to char *str=(char*)malloc(20*sizeof(char)); and it will work . On Wed, Aug 18, 2010 at 11:23 PM, Raj Jagvanshi raj.jagvan...@gmail.comwrote: wats d problem in my display() #includeiostream #includemalloc.h #include string.h using namespace std; struct node { char *name; struct node *next; }; typedef struct node Node; void createList(Node **head ) { char str[20]; char *p; coutEnter a String: ; gets (str) ; p = str; if((strlen(p))2) return; Node *temp=*head; Node *newnode=(Node*)malloc(sizeof(Node)); newnode-name=p; newnode-next=NULL; if(!temp) *head = newnode; else { while(temp-next) temp = temp-next; temp-next = newnode; } createList(head); } void display(Node *head) { cout\n; for( ; head ; head=head-next) cout\thead-name; cout\n; } int main() { Node *head=NULL; while(1) { cout\n\t\tMENU\n; cout0 : To exit.\n; cout1 : To create a linear link list.\n; cout2 : To display the list.\n; char choice; choice = getchar(); getchar(); if(choice=='0') break; switch(choice) { case '1': createList(head ); break; case '2': display(head); break; default: coutEnter valid choice.; } } system(pause); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Ram Narayan Das mob: +91 9177711195 -- 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] linked list
my display function print garbage value from begining On Thu, Aug 19, 2010 at 5:22 PM, vineeth mohan vm.vineethmo...@gmail.comwrote: void display(Node *head) { cout\n; for( ; head ; head=head-next) cout\thead-name; cout\n; } when head reaches last node condition head is true , then head will become head-next which is null , and it will try to print the name field from of a null value which is error On Wed, Aug 18, 2010 at 10:53 PM, Raj Jagvanshi raj.jagvan...@gmail.comwrote: wats d problem in my display() #includeiostream #includemalloc.h #include string.h using namespace std; struct node { char *name; struct node *next; }; typedef struct node Node; void createList(Node **head ) { char str[20]; char *p; coutEnter a String: ; gets (str) ; p = str; if((strlen(p))2) return; Node *temp=*head; Node *newnode=(Node*)malloc(sizeof(Node)); newnode-name=p; newnode-next=NULL; if(!temp) *head = newnode; else { while(temp-next) temp = temp-next; temp-next = newnode; } createList(head); } void display(Node *head) { cout\n; for( ; head ; head=head-next) cout\thead-name; cout\n; } int main() { Node *head=NULL; while(1) { cout\n\t\tMENU\n; cout0 : To exit.\n; cout1 : To create a linear link list.\n; cout2 : To display the list.\n; char choice; choice = getchar(); getchar(); if(choice=='0') break; switch(choice) { case '1': createList(head ); break; case '2': display(head); break; default: coutEnter valid choice.; } } system(pause); return 0; } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
@saikat ur algo fails with the test case a1=-2,-2 and a2=2,2 On Thu, Aug 19, 2010 at 10:22 PM, Saikat Debnath saikat@gmail.comwrote: 1. Add sum of squares of all numbers in respective groups, if equal goto step 2. 2. XOR all elements of both groups, (if==0) elements are same. On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote: @Nikhil Jindal: What you say is true for 2 numbers, but not for more than 2. 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36. Dave On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- 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. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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
[algogeeks] Re: Adobe Questions
With reference to the 2nd question i would lyk to add that the array size is not 3 but any numberwhat i meant to say was that the array nly contains 0,1,2 and no other number...and with reference to the 1st question it should be noted that there is no explicitly defined constructors involved with the class. -- 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] Longest Palindromic Substring
Can we use a trie here. Make first pass from left to right and construct the trie. Make second pass from right to left and look for the trie branch with maximum nodes that match the characters. On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote: Hi All, Givan a string, you have to find the longest palindromic substring. For ex: Longest Palindromic substring for abclevelabc is level. What is the most optimised solution possible? Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Enumerate restricted knight walks
Thanks. Can we find a closed form solution for that recurrence? On Thu, Aug 19, 2010 at 7:15 PM, Dave dave_and_da...@juno.com wrote: Let f(m,n) be the number of walks in an m x n board that is a subset of the M x N board. Then, for 2 = m = M and 2 = n = N, f satisfies the following recurrence relationship. f(m,n) = f(m-2,n-1) + f(m+2,n-1) + f(m-1,n-2) with the following boundary conditions: f(m,0) = f(m,1) = 0 for m = 1, 2, ..., M f(0,n) = f(1,n) = 0 for n = 1, 2, ..., N f(M+1,n) = F(M+2,n) = 0 for n = 1, 2, ..., N Dave On Aug 19, 7:40 am, summm sumant@gmail.com wrote: Find the number of ways a knight can move from top left square to bottom right square in an M*N Chess board with only the following moves allowed: a) 1 square right ; 2 squares down b) 1 square right ; 2 squares up and b) 2 squares right ; 1 square down. -- 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.