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
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.
I did it.
#include iostream
#include cmath
using namespace std;
int main(){
int n,ac,k,sum;
while(cinn n){
ac=0;
k=ceil((sqrt(1+8*n)-1)/2)-1;
ac+=k*(k+1)*(2*k+1)/6;
sum=(k+1)*(k+2)/2;
ac+=(k+1)*((k+1)-(sum-n));
coutn acendl;
}
}
Hi All
total number of coins = 1+(2+2)+(3+3+3)+(4+4+4+4)+(N+N+.N
times)
= 1+(2*2)+(3*3)+4*4+...+(N*N)
= (N*(N+1)*(2N+1))/6
Please do correct me if i am wrong
Regards
Praveen
On Thu, Feb 17, 2011 at 6:26
Question is to find the number of coins received on Nth day and not the
total number of coins received after N iterations.
On Wed, Feb 16, 2011 at 11:48 PM, Praveen praveen200...@gmail.com wrote:
Hi All
total number of coins = 1+(2+2)+(3+3+3)+(4+4+4+4)+(N+N+.N
times)
