Problem Link:Author: Pavel Sheftelevich Difficulty:Cakewalk PreRequisites:Implementation, Basic maths. Problem StatementConsider $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 ExplanationUse 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. SolutionSum 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, D1); // apply function F, D1 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]; // precomputation of sum of first N natural numbers void pre() { for(int i=1; i<=maxn; i++) { sumN[i] = sumN[i1] + 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 << "\n"; } return 0; } Time ComplexityVariable: $O(D)$, $O(maxn)$, $O(D*maxn)$ per test case. Space Complexityvariable: $O(1)$ to $O(maxn)$. Similar ProblemsSolution:Setter's solution can be found here Feel free to post comments if anything is not clear to you.
This question is marked "community wiki".
asked 15 Feb '16, 11:59

The recursive code given here is a bit wrong and it should have been: int sum(int d,int n) { if(d==0) { return n; } return sum(d1,n*(n+1)/2); } answered 05 Jul '18, 08:57
