Let f(n) = n(n+1)/2 We have to find n1 and n2 such that f(n1) < N <= f(n2) and n2 = n1 + 1. Solution is n2.
Can be done in O(1) as follows: Solve N = n(n+1)/2 for unknown n. Requires us to solve quadratic equation: n^2 + n - 2N = 0 Find positive root of the equation which could be a real number. n2 = ceil(n). On Wed, Feb 16, 2011 at 5:14 PM, Pedro Rezende <[email protected]> wrote: > It seems to be a very easy problem, but I'm not finding an *equation *that > solves it... could someone help me with the steps? > > Brief: > A king pays 1 gold coin to a knight on the first day. 2 gold coins for the > next 2 days, 3 gold coins for the next 3 days, and so on... > Given a day N, how much gold coins the knight must receive? > > Link: > http://acm.uva.es/archive/nuevoportal/data/problem.php?p=3045 > > Thank you all! :-) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
