Floor the larger number

Question

floor[1*e] + floor[2*e] + floor[3*e] + ... + floor[n*e],

where floor[x] is the largest integer that is not greater than x, and e is Euler's number: 2.7182818284..

Input

A single line which contains a single integer: n.

Output

A single line which contains a single integer which should be the answer.

Constraints

1 ≤ n ≤ 10 ^ 4000

Subtasks

Subtask #1 (50 points): 1 ≤ n ≤ 10 ^ 100

Subtask #2 (50 points): Original constraints.

Example

Input:

3

Output:

15

Explanation

floor[1*e] = floor[2.71828..] = 2.

floor[2*e] = floor[5.43656..] = 5.

floor[3*e] = floor[8.15484..] = 8.

So the answer is 2+5+8=15.

My Code

Scanner in=new Scanner(System.in);
int T = in.nextInt();
double e=2.7182818284;
long sum=0;

for (int t_i = 1; t_i <= T; t_i++) 
{

   sum=Math.floor(sum+t_i*e);
   // System.out.println(Math.floor(sum));

}
System.out.printf("%.0f",(sum));

This runs into a time-limit exceeded.

Answer 1

int, long and double are not precise enough. You should probably use BigInteger and/or BigDecimal instead.

Same problem with e=2.7182818284;. When you do 100000000000L*e you're already off by almost 6. And this is nothing compared to \$10^{100}\$.

Even if you use Math.E instead it's only 2.718281828459045. So you probably want to calculate e to an arbitrary precision (based on input n) instead. (Check here for a hint).

---

Note that none of those will help you with the time-limit-exceeded problem though. You'll have to find a smarter way so that you don't have to iterate all \$10^{4000}\$ numbers. Note that if you would add a number each millisecond and you ran the program for 300 years you would still only reach about \$10^{12}\$ or \$10^{13}\$. So no where close to what you want.

The best I can come up with is to keep track of the actual sum, the floored sum and the error on each order of magnitude.

So for n = 10, then n=100, then n=1000, ...

At each step you use the result of the previous one. That way you only need to do 10 iterations in the loop at that step to go up an order of magnitude.

Once you have those results you can calculate for any n the wanted result. The tricky part here is how to correct the error's at each step.

Even for \$n=10^{4000}\$ this should only result in O(10000) operations which (depending on your machine specs) runs in less than a minute. (Might also depend on how long calculations with BigInteger/BigDecimal take, I don't have much experience with those myself).

How to actually implement this I'll leave up to you, since this site is all about improving existing code, not just writing new code to solve the problem for you :)

Disclaimer: I did not test this myself yet, so not 100% sure that it will be fast enough even if implemented correctly.