[algogeeks] Re: n balls and k different colors 1=k=n
i didn't get anything plz elaborate On Oct 10, 10:44 am, Prunthaban Kanthakumar pruntha...@gmail.com wrote: Sterling numbers of second kind. On Sat, Oct 10, 2009 at 10:41 AM, vicky mehta...@gmail.com wrote: example: n=10,k=10 ans:1 n=30,k=7 ans: 475020 On Oct 10, 9:51 am, vicky mehta...@gmail.com wrote: u have to color n similar balls with k diff. colors , such that every color must be used atleast once find the no. of ways --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: n balls and k different colors 1=k=n
I just noticed that in your problem the balls are 'similar'. Then the solution is a simple composition and the answer is {n-1, k-1} where {n,k} stands for binomial coefficient. I will give a proof sometime later if needed. On Sat, Oct 10, 2009 at 11:22 AM, vicky mehta...@gmail.com wrote: i didn't get anything plz elaborate On Oct 10, 10:44 am, Prunthaban Kanthakumar pruntha...@gmail.com wrote: Sterling numbers of second kind. On Sat, Oct 10, 2009 at 10:41 AM, vicky mehta...@gmail.com wrote: example: n=10,k=10 ans:1 n=30,k=7 ans: 475020 On Oct 10, 9:51 am, vicky mehta...@gmail.com wrote: u have to color n similar balls with k diff. colors , such that every color must be used atleast once find the no. of ways --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
@sandeep notice that solution given on the given link doesn't satisfy the conditions given in the above question. @sharad Both lists may have duplicate values. So in this case it will better to hash the address of node instead of values. One other way is to maintain a flag in each of the node. In the begining flag will be 0 for all the items in both list. While traversing the first list, set the flags to 1. While traversing the seconds list,look for the item for which flag has been set. But this will also take additional o(n) space. I was thinking in line of reversing the first list while traversing it (it will use recursion). However, I couldn't make it work. Any thoughts? On Oct 10, 3:02 am, sandeep jain jainsandee...@gmail.com wrote: Here is one solutionhttp://geeksforgeeks.org/?p=2405 On Fri, Oct 9, 2009 at 9:00 AM, sharad kumar aryansmit3...@gmail.comwrote: space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? 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 algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Interesting array multiplication problem
There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n). --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Find the Grid row containing all 1's except intersection point in constant time
There is a n x n grid of 1's and 0's. Find the i, where i is the row containing all 1's, except the intersection point. Should do it in less than 25 comparisons? --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: n balls and k different colors 1=k=n
a very simple proof of the formula is using generating function for counting On Sat, Oct 10, 2009 at 3:08 PM, Prunthaban Kanthakumar pruntha...@gmail.com wrote: I just noticed that in your problem the balls are 'similar'. Then the solution is a simple composition and the answer is {n-1, k-1} where {n,k} stands for binomial coefficient. I will give a proof sometime later if needed. On Sat, Oct 10, 2009 at 11:22 AM, vicky mehta...@gmail.com wrote: i didn't get anything plz elaborate On Oct 10, 10:44 am, Prunthaban Kanthakumar pruntha...@gmail.com wrote: Sterling numbers of second kind. On Sat, Oct 10, 2009 at 10:41 AM, vicky mehta...@gmail.com wrote: example: n=10,k=10 ans:1 n=30,k=7 ans: 475020 On Oct 10, 9:51 am, vicky mehta...@gmail.com wrote: u have to color n similar balls with k diff. colors , such that every color must be used atleast once find the no. of ways -- nikhil- --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the Grid row containing all 1's except intersection point in constant time
Whats with the intersection point? Intersection of what two things are we talking about here? Row of 1s and column of 1s? On Sat, Oct 10, 2009 at 3:47 AM, Manisha pgo...@gmail.com wrote: There is a n x n grid of 1's and 0's. Find the i, where i is the row containing all 1's, except the intersection point. Should do it in less than 25 comparisons? -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interesting array multiplication problem
Nice solution Ramaswamy... --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Y shaped linklist
One other way will be using two pointers. step1) Take two pointers(p1 and p2 ), pointing to the beginning of list L1 and L2. step2) Now start moving both the pointers simultaneously and check whether they point to same node. If not, then move both pointers to next node. Step3) If any of pointer becomes NULL then set it to the beginning of another list. Lets say p1 becomes NULL, then set p1 to point to L2. Step4) Repeat the step2 After two traversals, both pointers will surely meet at intersection point. On Oct 10, 3:24 pm, Manisha pgo...@gmail.com wrote: @sandeep notice that solution given on the given link doesn't satisfy the conditions given in the above question. @sharad Both lists may have duplicate values. So in this case it will better to hash the address of node instead of values. One other way is to maintain a flag in each of the node. In the begining flag will be 0 for all the items in both list. While traversing the first list, set the flags to 1. While traversing the seconds list,look for the item for which flag has been set. But this will also take additional o(n) space. I was thinking in line of reversing the first list while traversing it (it will use recursion). However, I couldn't make it work. Any thoughts? On Oct 10, 3:02 am, sandeep jain jainsandee...@gmail.com wrote: Here is one solutionhttp://geeksforgeeks.org/?p=2405 On Fri, Oct 9, 2009 at 9:00 AM, sharad kumar aryansmit3...@gmail.comwrote: space comp O(n) time o(2n) both in terms of worst case On Fri, Oct 9, 2009 at 8:46 PM, ankur aggarwal ankur.mast@gmail.comwrote: @sharad wat about space ?? 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 algogeeks@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 -~--~~~~--~~--~--~---
[algogeeks] Re: Find the Grid row containing all 1's except intersection point in constant time
By intersection point, I mean intersection of ith row and ith coulmn. For instance, 1 0 0 1 1 1 1 1 0 Here the answer should be 3 as 3rd row contain all 1's except(3,3). On Oct 10, 9:15 pm, Ramaswamy R ramaswam...@gmail.com wrote: Whats with the intersection point? Intersection of what two things are we talking about here? Row of 1s and column of 1s? On Sat, Oct 10, 2009 at 3:47 AM, Manisha pgo...@gmail.com wrote: There is a n x n grid of 1's and 0's. Find the i, where i is the row containing all 1's, except the intersection point. Should do it in less than 25 comparisons? -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] 100!
find some of all the digits in number-100! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] optimum algo for second largest
can anyone give me algorithm for finding the second largest element in array using tournament method requiring n+logn-2 comparisons --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interesting array multiplication problem
traverse the array once and ge product of all elements , this is dividend now again traverse for each a[i] do division(divisor,a[i]) code for division without using / #includestdio.h int dividend, divisor, remainder; /* Division function Computes the quotient and remainder of two numbers using bit shifting */ int division(int tempdividend, int tempdivisor) { int quotient = 1; if (tempdivisor == tempdividend) { remainder = 0; return 1; } else if (tempdividend tempdivisor) { remainder = tempdividend; return 0; } while (tempdivisor = tempdividend) { /* Here divisor divisor and quotient */ tempdivisor = tempdivisor 1; quotient = quotient 1; } /* We have reached the point where divisor dividend, therefore divide divisor and quotient by two */ tempdivisor = tempdivisor 1; quotient = quotient 1; /* Call division recursively for the difference to get the exact quotient */ quotient = quotient + division(tempdividend - tempdivisor, divisor); return quotient; } /* Division of two numbers without using division operator */ main() { printf (\nEnter the Dividend: ); scanf(%d, dividend); printf(\nEnter the Divisor: ); scanf(%d, divisor); printf(\n%d / %d: quotient = %d, dividend, divisor, division(dividend, divisor)); printf(\n%d / %d: remainder = %d, dividend, divisor, remainder); } --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: 100!
hope you mean find *sum* of all the digits in number-100! :) 2009/10/11 vicky mehta...@gmail.com find some of all the digits in number-100! -- Reduce, Reuse and Recycle Regards, Vivek.S --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the Grid row containing all 1's except intersection point in constant time
On another thought, constant time complexity would not be possible with no constraints on the size of the matrix or any limitation on what possible data it would have. It wouldn't be possible to do it in 25 comparisons for a 1 Million x 1 Million grid. If there is no restriction on the data as well then we would be forced to scan through (in whatever way) all the n^2 values. On Sat, Oct 10, 2009 at 3:47 AM, Manisha pgo...@gmail.com wrote: There is a n x n grid of 1's and 0's. Find the i, where i is the row containing all 1's, except the intersection point. Should do it in less than 25 comparisons? -- Yesterday is History. Tomorrow is a Mystery. Today is a Gift! That is why it is called the Present :). http://sites.google.com/site/ramaswamyr --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: 100!
Project Euler!! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---