Re: [algogeeks] Sum of the Sequence
Thanks a ton. I found finite calculus very interesting and useful !
On Fri, Nov 6, 2009 at 11:35 AM, abhijith reddy abhijith200...@gmail.comwrote:
Thank you so much ! :)
On Fri, Nov 6, 2009 at 11:00 AM, Prunthaban Kanthakumar
pruntha...@gmail.com wrote:
On a related note,
The solution I gave you is to find the nth element in the kth series.
If you want to sum the first 'n' elements of the kth series (call the
function s(n,k)), then it is easy to see that,
*s(n,k) = f(n+1, k+1) - 1*
where f(n+1, k+1) is the (n+1)th element in the (k+1)th series.
This can also be easily done using the summation operator of 'finite
calculus'.
On Fri, Nov 6, 2009 at 10:50 AM, Prunthaban Kanthakumar
pruntha...@gmail.com wrote:
This is a 'finite calculus' (differences summations) problem.
You can solve it using difference operator (actually its inverse which
gives you the discrete integration which is nothing but summation).
If you do not know finite calculus, Google for it (or refer Concrete
Mathematics by Knuth).
The solution for any k is.
*f(n) = nC(k+1) + nC(k-1) + nC(k-3) + (all the way down to nC0 or
nC1 depends on k is odd or even).*
Here nCr is the binomial coefficient n choose r.
Eg: Let k = 3, n = 4
f(4) = 4C4 + 4C2 + 4C0 = 1 + 6 + 1 = 8
Another, k = 3 and n = 5
f(5) = 5C4 + 5C2 + 5C0 = 5 + 10 + 1 = 16
On Wed, Nov 4, 2009 at 11:23 AM, abhijith reddy
abhijith200...@gmail.com wrote:
Is there a way to find the sum of the Kth series ( Given below)
K=0 S={1,2,3,4,5,6,}
K=1 S={1,2,4,7,11,16..} common diff = 1,2,3,4 5 ...
K=2 S={1,2,4,8,15,26...} common diff = 1,2,4,7 11... (series with
K=1)
K=3 S={1,2,4,8,16,31...} common diff = 1,2,4,8 15... (series with
K=2)
Note that the common difference of Kth series is the (K-1) series
Any ideas ??
--
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.
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.
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
nikhil-
--
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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: aai + bj + ck =0
It is clearly O(n^2) . However i am sure there must be better methods available then this semi-naive method. Once i saw a problem which was on 4 lists and not three like here. So same algorithm on that case delievers O(n^3) and was giving me TLE. So yes , we should be able to do it nlogn somehow. On Sun, Nov 1, 2009 at 2:20 PM, Arun arunm...@gmail.com wrote: sorry it has to be k=k+1 in k=k-1 goto AGAIN as C is descending order. On Sun, Nov 1, 2009 at 1:48 AM, Arun arunm...@gmail.com wrote: I think daizi sheng is right, its O(n^2) if i rewrite his algo slgihtly, which makes me more clear A,B - sorted in ascending C in descending foreach(ai in A) ck = largest element in C j=1 AGAIN: if(ai + bj + ck == 0) algorithm over if(ai + bj + ck 0) k=k-1 goto AGAIN if(ai + bj + ck 0) j=j+1 On Sun, Nov 1, 2009 at 1:28 AM, anilkumarmyla anilkumarm...@gmail.comwrote: That way your solution takes more than O(N^2), because of the AGAIN loop. On Sun, Nov 1, 2009 at 1:09 PM, daizi sheng daizish...@gmail.comwrote: with all arrays sorted firstly, if you enumerate ai, bj in ascedning order, ck will be sure in descending order. foreach(ai in A) ck = largest element in C foreach(bj in B) AGAIN: if(ai + bj + ck == 0) algorithm over if(ai + bj + ck 0) ck change to its neighbor in C and goto AGAIN if(ai + bj + ck 0) continue checking next bj -- 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. 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- nikhil- -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Identify The f(x) :you are given a series of numbers(asked by MICROSOFT )?
This is a very common problem actually. And is most often solved using curve fitting only. We choose the curve to be polynomial of minimum degree and then use some interpolation method to get the exact polynomial. You may like to see the same problem at spoj: https://www.spoj.pl/problems/CMPLS/ On Fri, Oct 30, 2009 at 10:31 PM, Dave dave_and_da...@juno.com wrote: Kamal, wouldn't Microsoft want you to exhibit thinking outside the box on an interview question like this? If so, suggesting something like polynomial regression would be ho-hum. Furthermore, considering Occam's Razor, it would totally miss geometric sequences, the Fibonacci sequence, prime numbers, etc. I think that going to the database of integer sequences would be a much better response. Dave On Oct 30, 11:09 am, Kamal kannanju...@gmail.com wrote: In simple terms, if you are going to use only polynomial functions as f (x), this a polynomial curve fitting problem. Here, the input points are (1,2) (2,4) (3,6) and so on... There are many approaches to solve this. You can even consider other functions to model the series according to the need. A related well studied topic is Polynomial Regression (Regression Analysis in general) -- Kamal On Oct 30, 7:14 pm, Dave dave_and_da...@juno.com wrote: I would use a language, such as Perl, with which I could easily link to the web page for the Online Encyclopedia of Integer Sequences, using the URLhttp:// www.research.att.com/~njas/sequences/index.html?q=2,4,6,8,10,1.http://www.research.att.com/%7Enjas/sequences/index.html?q=2,4,6,8,10,1. .. (note that the sequence is imbeded in the URL) and output the response, which in this case includes 164 different sequences containing this sequence, the first few of which are the even numbers, the products of the digits of n, Values taken by totient function phi (m), n + product of nonzero digits of n, n + reversal of digits of n, and so forth. Dave On Oct 29, 7:19 am, Pawandeep bhatti.pawand...@gmail.com wrote: hello everyone , you are given a series of numbers like 2,4,6,8,10,12this is simple though nd u hve to identify that f(x) = x+ 2 for this series .. now can you write a program to identify the f(x) for any series of numbers.. // i know it is tough but don't say its not possible- 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 algogeeks@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 -~--~~~~--~~--~--~--- -- nikhil- -- 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Identify The f(x) :you are given a series of numbers(asked by MICROSOFT )?
Check google for Newton's interpolation method. That should help. cheers - nikhil On Fri, Oct 30, 2009 at 10:02 AM, Shiqing Shen ssq...@gmail.com wrote: match the sequence exactly? how to get that polynomial function, i am curious 2009/10/29, Vladimir Reshetnikov v.reshetni...@gmail.com: Any finite sequence of numbers can be matched by polynomial function. On Thu, Oct 29, 2009 at 3:19 PM, Pawandeep bhatti.pawand...@gmail.com wrote: hello everyone , you are given a series of numbers like 2,4,6,8,10,12this is simple though nd u hve to identify that f(x) = x+ 2 for this series .. now can you write a program to identify the f(x) for any series of numbers.. // i know it is tough but don't say its not possible -- 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: Pouring Water Problem
And as a matter of fact , this seems to be the best solution as well- clearly greedy fails here. e.g in the example given : we have cups of capacity 3, and 5. We can also use capacity of 5-3=2. So we can use 5 or 3 or 2 literse. The greedy choice to fill 4 liters should first fill in 3 litres and then it has no way of filling remaining 1 litre. Clearly best approach would be to fill using 2 litres twice. ( 2*4 = 8 operations) . However because last one is A-B type , we subtract one and get 7 operations. So only dp works and greedy fails. But however if you have capacities of A and B in some spcl constraint , we can use greedy as well. For example consider cups of size 4 litres and 6 litres. :P I think we can make greedy if A-B is smallest and divides both A and B. then we can always use greedy. // we need A-B to be smallest just because number of operations required are more for this . On Mon, Oct 26, 2009 at 12:06 PM, nikhil garg nikhilgar...@gmail.comwrote: We at any one step can measure only 3 quantities: A liters , B liters , or (A-B) litres. ( assuming AB) With every operation we have a cost associated: For A liter , we need 2 operations( Fill A , transfer from A to vessel) . For B liter , similarly we need 2 operations And for (A-B) litres we need 4 operations in general ( fill A , transfer A to B, transfer remaining A to vessel and spill B. ) However if this is the last operation , we dont need to empty B so in that case it would take 3 moves. But for the moment assume A takes 2 operations , B takes 2 and A-B takes 4. So see this as a variation of standard Coin Change problem or use simple DP to find the optimal number of operations. Check if in the optimal solution , last move is A-B , if yes, subtract 1 from the answer found ( we dont need to spill B now ) cheers On Mon, Oct 26, 2009 at 9:23 AM, shah zeb sftra...@yahoo.com wrote: http://eaziweb.blogspot.com/ Regards Shahzeb Farooq Chohan -- *From:* ShingRay masterrays...@gmail.com *To:* Algorithm Geeks algogeeks@googlegroups.com *Sent:* Sunday, October 25, 2009 14:59:58 *Subject:* [algogeeks] Pouring Water Problem Given two cups, one of which can contain A litres of water and the other can contain B litres of water, find out the minimum number of steps required to obtain C litres of water in a vessel. At the beginning both cups and the object vessel are empty. These are feasible operations: 1 emptying a cup 2 pouring water from a cup to the other or the vessel 3 filling a cup For example, when A is 3, B is 5 and C is 4, the minimum number of steps is 7. (*) You can fill B, and pour water from B to A, then pour water from B to the vessel. The three operations obtain 2 litres of water. We empty A and repeat (*). We obtain another 2 litres and it takes 7 steps. More examples: A B C minimum 1 2 1 2 1 2 9 10 3 5 12 7 6 7 20 6 - A*x + B*y = C If x, y are both no non-negative, it takes (x+y)*2 steps. If one of them is negative, it takes (x+y)*2-1 steps. We can iterate x from -max(A, B, C) to max(A, B, C) and get many x-y tuples, each of which denote a solution. The minimum solution is the best. I think the iteration range can be reduce. What is a more effective algorithm? -- New Email addresses available on Yahoo! http://sg.rd.yahoo.com/aa/mail/domainchoice/mail/signature/*http://mail.promotions.yahoo.com/newdomains/aa/ Get the Email name you've always wanted on the new @ymail and @rocketmail. Hurry before someone else does! -- nikhil- -- 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 index of a number in a sorted array
probably the only entirey different approach ( except small variations in Bsearch ) is use of Hashing ( or for that matter , HashMaps ) On Sun, Oct 25, 2009 at 1:36 PM, harit agarwal agarwalha...@gmail.comwrote: the only other way can be the jump exponentially during search as in binary search a[mid] is checked so if a[mid]!=x then make low=highest index of a[mid]!=x this will reduce the comparisionsin binary search ex-1,1,1,2,2,2,3,3,3,4,4,5,5(13 elements) let's search for 4 modify binary search a[mid]=3 // !=4 such that mid=highest index of 3 in array and make low=mid+1 this way it can be donejust modify binary search. -- 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: Pouring Water Problem
We at any one step can measure only 3 quantities: A liters , B liters , or (A-B) litres. ( assuming AB) With every operation we have a cost associated: For A liter , we need 2 operations( Fill A , transfer from A to vessel) . For B liter , similarly we need 2 operations And for (A-B) litres we need 4 operations in general ( fill A , transfer A to B, transfer remaining A to vessel and spill B. ) However if this is the last operation , we dont need to empty B so in that case it would take 3 moves. But for the moment assume A takes 2 operations , B takes 2 and A-B takes 4. So see this as a variation of standard Coin Change problem or use simple DP to find the optimal number of operations. Check if in the optimal solution , last move is A-B , if yes, subtract 1 from the answer found ( we dont need to spill B now ) cheers On Mon, Oct 26, 2009 at 9:23 AM, shah zeb sftra...@yahoo.com wrote: http://eaziweb.blogspot.com/ Regards Shahzeb Farooq Chohan -- *From:* ShingRay masterrays...@gmail.com *To:* Algorithm Geeks algogeeks@googlegroups.com *Sent:* Sunday, October 25, 2009 14:59:58 *Subject:* [algogeeks] Pouring Water Problem Given two cups, one of which can contain A litres of water and the other can contain B litres of water, find out the minimum number of steps required to obtain C litres of water in a vessel. At the beginning both cups and the object vessel are empty. These are feasible operations: 1 emptying a cup 2 pouring water from a cup to the other or the vessel 3 filling a cup For example, when A is 3, B is 5 and C is 4, the minimum number of steps is 7. (*) You can fill B, and pour water from B to A, then pour water from B to the vessel. The three operations obtain 2 litres of water. We empty A and repeat (*). We obtain another 2 litres and it takes 7 steps. More examples: A B C minimum 1 2 1 2 1 2 9 10 3 5 12 7 6 7 20 6 - A*x + B*y = C If x, y are both no non-negative, it takes (x+y)*2 steps. If one of them is negative, it takes (x+y)*2-1 steps. We can iterate x from -max(A, B, C) to max(A, B, C) and get many x-y tuples, each of which denote a solution. The minimum solution is the best. I think the iteration range can be reduce. What is a more effective algorithm? -- New Email addresses available on Yahoo! http://sg.rd.yahoo.com/aa/mail/domainchoice/mail/signature/*http://mail.promotions.yahoo.com/newdomains/aa/ Get the Email name you've always wanted on the new @ymail and @rocketmail. Hurry before someone else does! -- 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: 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: sum of subsequence.
This is a simple dp problem .
define for each i following 2 quantities :
best1[i] : best sum in similar constraint of first i elements only when last
( ith ) term is always included
best2[i] : best sum in similar constraint of the first i elements only when
last (ith ) term is NOT included
so we can define best1 and best2 in terms of smaller bests like this :
best1[i] : max{ (best2[i-1]+a[i]) , a[i] }
best2[i]: max{ (best1[i-1] + a[i] ) , (best2[i-1]+a[i] ) , a[i] }
best1[0]=a[0] ans best2[0]=0;
finally we are concerned in :
max { best1[last] , best2[last] }
so we can find the answer in O(n)
On Fri, Oct 9, 2009 at 9:26 AM, ankur aggarwal ankur.mast@gmail.comwrote:
2. Given an array all of whose elements are positive numbers, find the
maximum sum of a subsequence with the constraint that no 2 numbers in the
sequence should be adjacent in the array.
i) 3 2 7 10 should return 13 (sum of 3 and 10)
ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
--
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
-~--~~~~--~~--~--~---
