taekout
BAN USERI don't see how to post a solution. So I post it as a reply. Sorry about that.
Below is the pseudo code. The idea is that just get the optimal case. (step every time.) If it does not step on K, good. That should be the optimal solution.
If it happens to step on Kth stair, the optimal case must be all the steps without the first step(1st step).
Why? Proof below:
Proof :
If we step on Kth stairs, there must be a case without Ith step, we cannot reach K.
We always avoid Kth stair by not stepping the 1st step since K != (K-1).
For an arbitrary I, I >= 1 is always true,
thus SumFrom1ToN - 1 >= SumFrom1ToN - I is always true.
Thus, skipping the 1st step is always optimal.
Solution :
long long sum = 0;
for(int i = 0 ; i < k ; i++)
{
sum += i;
if( sum > K ) {
return SumFrom1ToN(N); //Because this is optimal case. Just stepping every time does happen to step on Kth stair.
}
else if( sum == K ) { // Stepping on K, so we could just not step the first step.
return SumFrom1ToN(N) - 1;
}
}
return -1; // error. impossible to get here.
- taekout June 11, 2015I don't see how to post a solution. So I post it as a reply. Sorry about that.
Below is the pseudo code. The idea is that just get the optimal case. (step every time.) If it does not step on K, good. That should be the optimal solution.
If it happens to step on Kth stair, the optimal case must be all the steps without the first step(1st step).
Why? Proof below:
Proof :
If we step on Kth stairs, there must be a case without Ith step, we cannot reach K.
We always avoid Kth stair by not stepping the 1st step since K != (K-1).
For an arbitrary I, I >= 1 is always true,
thus SumFrom1ToN - 1 >= SumFrom1ToN - I is always true.
Thus, skipping the 1st step is always optimal.
Solution :
long long sum = 0;
for(int i = 0 ; i < k ; i++)
{
sum += i;
if( sum > K ) {
return SumFrom1ToN(N); //Because this is optimal case. Just stepping every time does happen to step on Kth stair.
}
else if( sum == K ) { // Stepping on K, so we could just not step the first step.
return SumFrom1ToN(N) - 1;
}
}
return -1; // error. impossible to get here.
Repthubmorfin, Android Engineer at ABC TECH SUPPORT
I am currently working as a safety-focused Service Technician from Red Bank. I execute routine maintenance work while advising clients ...
RepHuge collection of cheap ammo for Rifle, Handgun, Shotgun & Rimfire from top brands you are looking for.
RepRichardWParks, Accountant at ADP
I also have a dynamic programming solution.
- taekout June 11, 2015It works for general cases. (multiple Ks).
It runs better than exponential complexity. (K^3)