### Problem Link:

**Author:** Pavel Sheftelevich

**Tester:** Kanstantsin Sokal

**Editorialist:** Sunny Aggarwal

### Difficulty:

Cakewalk

### Pre-Requisites:

Implementation, Basic maths.

### Problem Statement

Consider F(N) a function denoting the sum of first N natural numbers. Given N and D, Apply function F, D times and calculate the following value F(F(F( ... D times(N)))).

### Brief Explanation

Use well known recurrence for the sum of first N natural numbers i.e N * (N+1) / 2 and calculate the value by applying it D times.

### Solution

Sum of first N natural number is given by N * (N+1) / 2. Using this, we can calculate the required answer as follows:

**Iterative Code**

// helper function to find the sum of first N natural numbers int sum_of_first_N_natural_numbers(int N) { return (N * (N+1) / 2); } // computing required answer int F(int N, int D) { while(D --) { applying function D times N = sum_of_first_N_natural_numbers(N); } }

**Recursive Code**

int F(int N, int D) { if( D == 0 ) { return N; // don't need to apply function further as D = 0 } return F(N * (N+1)/2, D-1); // apply function F, D-1 times on the new value of N. }

Note that constraints in this are quite low i.e N \le 4 \And D \le 4. Therefore, an efficient solution without using the recurrence for first N natural numbers can pass the test data.

Alternatively, We can pre compute the sum of first N natural numbers in a table and can make use of table for faster solution.

**C ++ Code:**

const int maxn = 1186570; int sumN[maxn+10]; // pre-computation of sum of first N natural numbers void pre() { for(int i=1; i<=maxn; i++) { sumN* = sumN[i-1] + i; } } int main() { pre(); int T; cin >> T; while( T-- ) { int N; int D; cin >> N >> D; int ans = N; while(D -- ) { ans = sumN[ans]; } cout << ans << " "; } return 0; }

### Time Complexity

**Variable:**

O(D), O(maxn), O(D*maxn) per test case.

### Space Complexity

**variable:** O(1) to O(maxn).

### Similar Problems

### Solution:

Setterâ€™s solution can be found here

Testerâ€™s solution can be found here

**Feel free to post comments if anything is not clear to you.**