Re: [algogeeks] Multiplication of two numbers
If a and b are the numbers then dig = log10(a) + log10(b); if dig has some fractional part then number of digits is dig + 1 else dig. On Mon, Sep 20, 2010 at 11:19 AM, sumant hegde sumant@gmail.com wrote: Adding to the partial solution, if x, y are first digits, and x*y + x + y 10, the result will be a+b -1 digits. If not, u will need a complex logic to solve On Mon, Sep 20, 2010 at 10:50 AM, rahul patil rahul.deshmukhpa...@gmail.com wrote: A partial solution is , if you multiply first digits of two nos and result is greater than 10 then surely result will be a+b digits If not, according to me, u will need a complex logic to solve. On Mon, Sep 20, 2010 at 10:41 AM, Srinivas lavudyasrinivas0...@gmail.com wrote: how to find the no. of digits in the product of two numbers without multiplying?? if a is the number of digits in A and if b is the number of digits in B the number of digits in A*B is either a+b or a+b-1 but how to find the exact one? -- You received this message because you are subscribed to the Google Groups Algorithm 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, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm 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: print largest continue subsequent in int array
Just tell me wats the answer for thissequence 1, 3 ,5, -1, -2 ,0, 7 . On 9/20/10, Dave dave_and_da...@juno.com wrote: Krunal: If the array contains only negative numbers, shouldn't the subsequence with the largest sum be the empty subsequence? Dave On Sep 19, 5:45 am, Krunal Modi krunalam...@gmail.com wrote: @LG Jayaram : check for -5 -4 -3 -2 -1 answer should be : -1 -- You received this message because you are subscribed to the Google Groups Algorithm 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] recursion to remove duplicate characters in a string
Yes ur correct...it will require some extra spacebst can be represented in the array form ritelet me think in tht logic. On 9/19/10, Umer Farooq the.um...@gmail.com wrote: creating a bst would require extra space. You can do this with an array of char dude. On Sun, Sep 19, 2010 at 3:31 PM, LG JAYARAM . lgj...@gmail.com wrote: hi buddy ...Im clear with the ideahereby I share the concept... wat exactly need to be done to solve this task isbetter create a Binary search tree...the Binary search tree will not allow duplicates and If u perform a inorder traversalu can get the result...the task is oversimple and thts it. On Sat, Sep 18, 2010 at 11:12 PM, jagadish jagadish1...@gmail.comwrote: You are given a string which is sorted.. Write a recursive function to remove the duplicate characters in the string. eg: potatoeos output: potaes NO extraspace like hash/ bitmaps.. -- You received this message because you are subscribed to the Google Groups Algorithm 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. -- Umer -- You received this message because you are subscribed to the Google Groups Algorithm 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] Multiplication of two numbers
On Mon, Sep 20, 2010 at 1:15 PM, Baljeet Kumar baljeetk...@gmail.comwrote: If a and b are the numbers then dig = log10(a) + log10(b); if dig has some fractional part then number of digits is dig + 1 else dig. found this correct onw On Mon, Sep 20, 2010 at 11:19 AM, sumant hegde sumant@gmail.comwrote: Adding to the partial solution, if x, y are first digits, and x*y + x + y 10, the result will be a+b -1 digits. If not, u will need a complex logic to solve if we take 30 * 33 as an example then it is (3*3 + 3+3 ) 10 which says ans will be 4 digit but ans is 990 which is 3 digit. On Mon, Sep 20, 2010 at 10:50 AM, rahul patil rahul.deshmukhpa...@gmail.com wrote: A partial solution is , if you multiply first digits of two nos and result is greater than 10 then surely result will be a+b digits If not, according to me, u will need a complex logic to solve. On Mon, Sep 20, 2010 at 10:41 AM, Srinivas lavudyasrinivas0...@gmail.com wrote: how to find the no. of digits in the product of two numbers without multiplying?? if a is the number of digits in A and if b is the number of digits in B the number of digits in A*B is either a+b or a+b-1 but how to find the exact one? -- You received this message because you are subscribed to the Google Groups Algorithm 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, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm 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. -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm 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: print largest continue subsequent in int array
@Dave : We have to find any element. So whichever is larger has to be the answer.Hence, -1 -- You received this message because you are subscribed to the Google Groups Algorithm 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: print largest continue subsequent in int array
@LG JAYARAM: It is 7. -- You received this message because you are subscribed to the Google Groups Algorithm 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] Multiplication of two numbers
@Naveen:
Yes you are right, the answer is not fully correct.
ans = integral part of ((log10(a)+log10(b) +1) {floor not ceiling}.
On Mon, Sep 20, 2010 at 4:11 PM, Naveen Agrawal nav.coo...@gmail.comwrote:
@Baljeet
I think your Answer is not fully correct
It should be : ans=ceil(log10(a)+log10(b) +1)
Naveen Agarwal
--
You received this message because you are subscribed to the Google Groups
Algorithm 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.
--
Baljeet Kumar
B.Tech, IV Year
Computer Science Engineering.
Indian Institute of Technology, Roorkee
Ph. no. +91-9456318689
--
You received this message because you are subscribed to the Google Groups
Algorithm 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: print largest continue subsequent in int array
@Krunal: can u explain hwz 7 On Mon, Sep 20, 2010 at 6:02 PM, Krunal Modi krunalam...@gmail.com wrote: @LG JAYARAM: It is 7. -- You received this message because you are subscribed to the Google Groups Algorithm 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: Multiplication of two numbers
@Rahul. No. Considering your example 33*30, x*y + x + y = 3*3 + 3 + 3 = 15 is not 10, so, as specified by Sumant, u will need a complex logic to solve. Dave On Sep 20, 5:31 am, rahul patil rahul.deshmukhpa...@gmail.com wrote: On Mon, Sep 20, 2010 at 1:15 PM, Baljeet Kumar baljeetk...@gmail.comwrote: If a and b are the numbers then dig = log10(a) + log10(b); if dig has some fractional part then number of digits is dig + 1 else dig. found this correct onw On Mon, Sep 20, 2010 at 11:19 AM, sumant hegde sumant@gmail.comwrote: Adding to the partial solution, if x, y are first digits, and x*y + x + y 10, the result will be a+b -1 digits. If not, u will need a complex logic to solve if we take 30 * 33 as an example then it is (3*3 + 3+3 ) 10 which says ans will be 4 digit but ans is 990 which is 3 digit. On Mon, Sep 20, 2010 at 10:50 AM, rahul patil rahul.deshmukhpa...@gmail.com wrote: A partial solution is , if you multiply first digits of two nos and result is greater than 10 then surely result will be a+b digits If not, according to me, u will need a complex logic to solve. On Mon, Sep 20, 2010 at 10:41 AM, Srinivas lavudyasrinivas0...@gmail.com wrote: how to find the no. of digits in the product of two numbers without multiplying?? if a is the number of digits in A and if b is the number of digits in B the number of digits in A*B is either a+b or a+b-1 but how to find the exact one? -- You received this message because you are subscribed to the Google Groups Algorithm 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, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm 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. -- Regards, Rahul Patil- 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: number of inversion pairs
use a bst and insert in it reverse of array. use a count in bst node
and incr count at each right child insertion
On Sep 14, 11:00 am, Shiv ... shivsinha2...@gmail.com wrote:
A pseudo code-
int n; //= number of inputs.
cin*a; // the inputs.
int ** invArr;
*inVArr[n-1] = NULL;
//initialise all the elemnts with Null to be safe.
for(int i = n-1; i =0; i--) {
for (int j = i; j n; j++ )
{
if(a[i] == a[j]) {
*invArr[i] = *invArr[j];
break;
}
if( a[i] a[j]) {
invArr[i][0] = a[j];
*invArr[i] + 1 = *invArr[j];
break;
}
} //inner for
}//outer for
//print invArr;
==
Please note the worst case would still be O(n^2). But I think average will
be significantly improved. (I will be happy if someone can do these
calculations. :)) )
And this is such a pseudo code. I will be grateful if someone can make this
run-able.
-thanks.
On Tue, Sep 14, 2010 at 2:34 AM, Wladimir Tavares
wladimir...@gmail.comwrote:
My two cents
If you were asked in O(n log n)
you have to modified the merge sort algorithm for count the number of
inversion!
Wladimir Araujo Tavares
http://www.si.ufc.br/~wladimirhttp://www.si.ufc.br/%7Ewladimir/
Fiz uma faculdade! Só não fiz a segunda porque acabaram os tijolos.
On Mon, Sep 13, 2010 at 1:05 PM, sharad kumar
aryansmit3...@gmail.comwrote:
linear decreasing sub sequence problem
On Mon, Sep 13, 2010 at 9:10 PM, Raj N rajn...@gmail.com wrote:
Given an array of n integers find all the inversion pairs in O(n)
Inversion pair is one where a[i]a[j], ij
--
You received this message because you are subscribed to the Google Groups
Algorithm 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.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm 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] point lies inside or outside of triangle..
Initially we have given three point A , B, C in plane represent three nodes of triangle, now given another point Z which lies in same plane, find out whether that point lies on/inside the triangle or outside of triangletry to get in min time and space complexity -- Thanks Regards Umesh kewat -- You received this message because you are subscribed to the Google Groups Algorithm 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] Point lies inside or outside of triangle?
Initially we have given three point A , B, C in plane represent three nodes of triangle, now given another point Z which lies in same plane, find out whether that point lies on/inside the triangle or outside of triangletry to get in minimum time and space complexity -- Thanks Regards Umesh kewat -- You received this message because you are subscribed to the Google Groups Algorithm 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] Point lies inside or outside of triangle?
here is the hint we can easily solve this draw a triangle draw a point is inside the triangle connect the three vertices of the triangle with this point you will get three small triangle if ( area(big triangle)== sum of area of small triangles) then the point is inside the triangle else it is outside the triangle On Mon, Sep 20, 2010 at 10:02 PM, umesh umesh1...@gmail.com wrote: Initially we have given three point A , B, C in plane represent three nodes of triangle, now given another point Z which lies in same plane, find out whether that point lies on/inside the triangle or outside of triangletry to get in minimum time and space complexity -- Thanks Regards Umesh kewat -- You received this message because you are subscribed to the Google Groups Algorithm 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. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm 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] Point lies inside or outside of triangle?
One way would be : Create equation of three sides of the triangle Now check for this point if it lies on left/right of the line (do it for each of the lines)... On Mon, Sep 20, 2010 at 9:06 PM, Praveen Baskar praveen200...@gmail.comwrote: here is the hint we can easily solve this draw a triangle draw a point is inside the triangle connect the three vertices of the triangle with this point you will get three small triangle if ( area(big triangle)== sum of area of small triangles) then the point is inside the triangle else it is outside the triangle On Mon, Sep 20, 2010 at 10:02 PM, umesh umesh1...@gmail.com wrote: Initially we have given three point A , B, C in plane represent three nodes of triangle, now given another point Z which lies in same plane, find out whether that point lies on/inside the triangle or outside of triangletry to get in minimum time and space complexity -- Thanks Regards Umesh kewat -- You received this message because you are subscribed to the Google Groups Algorithm 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. -- By B. Praveen -- You received this message because you are subscribed to the Google Groups Algorithm 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, Saurabh -- You received this message because you are subscribed to the Google Groups Algorithm 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: Multiplication of two numbers
Wonder if this works: x = A / 10^(a-1) // take it as a decimal value itself y = B / 10^(b-1) // take it as a decimal value itself if x * y = 10.0 return (a+b) else return (a+b-1) One advantage of the above method is that it can be done mentally. On Sep 20, 10:47 am, Dave dave_and_da...@juno.com wrote: @Rahul. No. Considering your example 33*30, x*y + x + y = 3*3 + 3 + 3 = 15 is not 10, so, as specified by Sumant, u will need a complex logic to solve. Dave On Sep 20, 5:31 am, rahul patil rahul.deshmukhpa...@gmail.com wrote: On Mon, Sep 20, 2010 at 1:15 PM, Baljeet Kumar baljeetk...@gmail.comwrote: If a and b are the numbers then dig = log10(a) + log10(b); if dig has some fractional part then number of digits is dig + 1 else dig. found this correct onw On Mon, Sep 20, 2010 at 11:19 AM, sumant hegde sumant@gmail.comwrote: Adding to the partial solution, if x, y are first digits, and x*y + x + y 10, the result will be a+b -1 digits. If not, u will need a complex logic to solve if we take 30 * 33 as an example then it is (3*3 + 3+3 ) 10 which says ans will be 4 digit but ans is 990 which is 3 digit. On Mon, Sep 20, 2010 at 10:50 AM, rahul patil rahul.deshmukhpa...@gmail.com wrote: A partial solution is , if you multiply first digits of two nos and result is greater than 10 then surely result will be a+b digits If not, according to me, u will need a complex logic to solve. On Mon, Sep 20, 2010 at 10:41 AM, Srinivas lavudyasrinivas0...@gmail.com wrote: how to find the no. of digits in the product of two numbers without multiplying?? if a is the number of digits in A and if b is the number of digits in B the number of digits in A*B is either a+b or a+b-1 but how to find the exact one? -- You received this message because you are subscribed to the Google Groups Algorithm 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, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm 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. -- Regards, Rahul Patil- 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] Arrays
Two unsorted arrays are given A[n] and B[n+1]. Array A contains n integers and B contains n+1 integers of which n are same as in array B but in different order and one extra element x. Write an optimized algorithm to find the value of element x. Use only one pass of both arrays A and B. -- You received this message because you are subscribed to the Google Groups Algorithm 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: point lies inside or outside of triangle..
This is okay, but does more math than necessary. Here's another
approach:
// Return 0 if p is left of a-b, 2 if right of a-b, and 1 if on a-
b.
int side(PT *p, PT *a, PT *b)
{
float d = (p.x-a.x) * (b.y-a.y) - (p.y-a.y) * (b.x-a.x);
return d 0 ? 0 : d 0 ? 2 : 1;
}
// This table treats points on the edges as inside. Just redo the
// table to count them as outside.
bool inside_polygon(PT *p, PT *a, PT *b, PT *c)
{
bool p[3][3][3] =
{{ // 0, ...
// 0 =00
{ true, true, false }, // 0, ...
{ true, true, false }, // =0
{ false, false, false }}, // 0
{{ // =0,
{ true, true, false }, // 0
{ true, true, true }, // =0
{ false, true, true }}, // 0
{{ // 0,
{ false, false, false }, // 0
{ false, true, true }, // =0
{ false, true, true }}}; // 0
return p[side(p, a, b)][side(p, b, c)][side(p, c, a)];
}
This relies on the facts 1) if a, b, c if abc are given in CCW order,
then all three side values are 0 iff the point is inside; and 2) if
they are given in CW order, then the side values are 2 iff the point
is inside; 3) the values can't be 000 if the vertices are in CCW order
(except for the point at infinity, which doesn't exist in a computer);
and 4) the values can't be 222 if the vertices are given in CW order
(again except for the point at infinity).
On Sep 20, 4:20 pm, Naveen Agrawal nav.coo...@gmail.com wrote:
Take intersection point of triangle as a,b,c
And the testing point as p
boolean SameSide(p,s,t ,u)
if s p lies on same side //to check same side form equation
using t and u and then evaluate the value of point
return true //ps,if both gives same
sign(+ve or -ve) value then they are on same side
else
return false
void PointInTriangle(p, a,b,c)
if (SameSide(p,a, b,c) SameSide(p,b, a,c) SameSide(p,c, a,b))
Inside the triange
else
outside triangle
--
You received this message because you are subscribed to the Google Groups
Algorithm 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] Arrays
add up all the elements in array A say sumA and array B say sumB ,substract the sumA from sumB... You'll get the element. On Tue, Sep 21, 2010 at 5:36 AM, Anand anandut2...@gmail.com wrote: Two unsorted arrays are given A[n] and B[n+1]. Array A contains n integers and B contains n+1 integers of which n are same as in array B but in different order and one extra element x. Write an optimized algorithm to find the value of element x. Use only one pass of both arrays A and B. -- You received this message because you are subscribed to the Google Groups Algorithm 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: Point lies inside or outside of triangle?
Following up two of my postings. Sorry, but I gave the wrong system of equations in my first posting, and then solved that incorrect system in my second. The system of equations should be xa * a + xb * b + xc * c = xz ya * a + yb * b + yc * c = yz a + b + c = 1 Then the following are the expressions that are all the same sign if the point is in the triangle: expression_1 = xz * (yb - yc) + xb * (yc - yz) + xc * (yz - yb) expression_2 = xa * (yz - yc) + xz * (yc - ya) + xc * (ya - yz) expression_3 = xa * (yb - yz) + xb * (yz - ya) + xz * (ya - yb) Sorry for the mistakes in the earlier posts. Dave On Sep 20, 3:17 pm, Dave dave_and_da...@juno.com wrote: Following up on my own posting, if these three expressions all have the same sign, the point is in the triangle. If any of them is zero, the point is on the boundary, and if any of them have opposite signs, then the point is not in the triangle: expression_1 = xz * yb - xb * yz + xb - xz + yz - yb expression_2 = xa * yz - xz * ya + xz - xa + ya - yz expression_3 = xa * (yb - yz) + xb * (yz - ya) + xz * (ya - yb) These expressions are the numerators that result when solving the three equations in my previous posting by Cramer's Rule. There is no reason to calculate the denominator and divide; if the triangle really is a triangle (i.e., if the three points of the triangle are not collinear), then the denominator is nonzero. At least one of the numerators has to have the same sign as the denominator, since otherwise all solution unknowns would be negative but they sum to 1. If any numerator is of the opposite sign, then the corresponding solution unknown is negative, indicating that the point is not in the triangle. Dave On Sep 20, 12:27 pm, Dave dave_and_da...@juno.com wrote: Use Barycentric Coordinates: Let the point A have coordinates (xa, ya), and similar for points B, C, and Z. Solve the system of linear equations xa * a + xb * b + c = xz ya * a + yb * b + c = yz a + b + c = 1 for a, b, and c. If all of a, b, and c are = 0, the point is in the triangle ( 0) or on the boundary (= 0). Otherwise, the point is outside the triangle. Dave On Sep 20, 10:02 am, umesh umesh1...@gmail.com wrote: Initially we have given three point A , B, C in plane represent three nodes of triangle, now given another point Z which lies in same plane, find out whether that point lies on/inside the triangle or outside of triangletry to get in minimum time and space complexity -- Thanks Regards Umesh kewat- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Arrays
There can be overflow in case of adding up all the elements. Use Xor
instead.
int result = 0;
for (int i = 0; i n ;i++){
result ^= A[i]^B[i];
}
result ^= B[i];
result is the number we need.
On Tue, Sep 21, 2010 at 9:48 AM, vishal raja vishal.ge...@gmail.com wrote:
add up all the elements in array A say sumA and array B say sumB
,substract the sumA from sumB... You'll get the element.
On Tue, Sep 21, 2010 at 5:36 AM, Anand anandut2...@gmail.com wrote:
Two unsorted arrays are given A[n] and B[n+1]. Array A contains n integers
and B contains n+1 integers of which n are same as in array B but in
different order and one extra element x. Write an optimized algorithm to
find the value of element x. Use only one pass of both arrays A and B.
--
You received this message because you are subscribed to the Google Groups
Algorithm 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.
--
Baljeet Kumar
--
You received this message because you are subscribed to the Google Groups
Algorithm 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] Arrays
There can be overflow in case of adding up all the elements. Use Xor
instead.
int result = 0;
for (int i = 0; i n ;i++){
result ^= A[i]^B[i];
}
result ^= B[n]; === (correction)
result is the number we need.
On Tue, Sep 21, 2010 at 9:48 AM, vishal raja vishal.ge...@gmail.comwrote:
add up all the elements in array A say sumA and array B say sumB
,substract the sumA from sumB... You'll get the element.
On Tue, Sep 21, 2010 at 5:36 AM, Anand anandut2...@gmail.com wrote:
Two unsorted arrays are given A[n] and B[n+1]. Array A contains n
integers and B contains n+1 integers of which n are same as in array B but
in different order and one extra element x. Write an optimized algorithm to
find the value of element x. Use only one pass of both arrays A and B.
--
You received this message because you are subscribed to the Google Groups
Algorithm 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.
--
Baljeet Kumar
--
Baljeet Kumar
--
You received this message because you are subscribed to the Google Groups
Algorithm 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: point lies inside or outside of triangle..
@gene i didn't understand the boolean thing in your algo,
Say triangle is ABC, say Point is p
Algo goes like this,
for side AB
1. calculate cross product of(p-A)*(B-A)[ Which is nothing but the side
function in gene algo] See the sign.
2. calculate the cross product of (C-A)*(B-A) . See the sign if it is not
same then say the point lies outside.
3. If the signs are same repeat the step1 from other sides.
The funda here is if a point is inside a triangle then cross product of the
point joining any vertex to the side containing that vertex, should point in
the same side (up or below), with reference to cross product of this vertex
to any reference point(C for AB because they are in the same plane) with the
side (AB) should also point in the same direction, When this process is
repeated for all sides then we can say that the point is inside the
triangle.
On Tue, Sep 21, 2010 at 6:09 AM, Gene gene.ress...@gmail.com wrote:
This is okay, but does more math than necessary. Here's another
approach:
// Return 0 if p is left of a-b, 2 if right of a-b, and 1 if on a-
b.
int side(PT *p, PT *a, PT *b)
{
float d = (p.x-a.x) * (b.y-a.y) - (p.y-a.y) * (b.x-a.x);
return d 0 ? 0 : d 0 ? 2 : 1;
}
// This table treats points on the edges as inside. Just redo the
// table to count them as outside.
bool inside_polygon(PT *p, PT *a, PT *b, PT *c)
{
bool p[3][3][3] =
{{ // 0, ...
// 0 =00
{ true, true, false }, // 0, ...
{ true, true, false }, // =0
{ false, false, false }}, // 0
{{ // =0,
{ true, true, false }, // 0
{ true, true, true }, // =0
{ false, true, true }}, // 0
{{ // 0,
{ false, false, false }, // 0
{ false, true, true }, // =0
{ false, true, true }}}; // 0
return p[side(p, a, b)][side(p, b, c)][side(p, c, a)];
}
This relies on the facts 1) if a, b, c if abc are given in CCW order,
then all three side values are 0 iff the point is inside; and 2) if
they are given in CW order, then the side values are 2 iff the point
is inside; 3) the values can't be 000 if the vertices are in CCW order
(except for the point at infinity, which doesn't exist in a computer);
and 4) the values can't be 222 if the vertices are given in CW order
(again except for the point at infinity).
On Sep 20, 4:20 pm, Naveen Agrawal nav.coo...@gmail.com wrote:
Take intersection point of triangle as a,b,c
And the testing point as p
boolean SameSide(p,s,t ,u)
if s p lies on same side //to check same side form equation
using t and u and then evaluate the value of point
return true//ps,if both gives same
sign(+ve or -ve) value then they are on same side
else
return false
void PointInTriangle(p, a,b,c)
if (SameSide(p,a, b,c) SameSide(p,b, a,c) SameSide(p,c, a,b))
Inside the triange
else
outside triangle
--
You received this message because you are subscribed to the Google Groups
Algorithm 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.
