×

PPSUM - Editorial

Author: Pavel Sheftelevich
Tester: Kanstantsin Sokal
Editorialist: Sunny Aggarwal

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);
}
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[i] = 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 << "\n";
}
return 0;
}


Time Complexity

Variable: $O(D)$, $O(maxn)$, $O(D*maxn)$ per test case.

Space Complexity

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

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.

This question is marked "community wiki".

1.7k11730
accept rate: 11%

19.8k350498541

 0 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(d-1,n*(n+1)/2); } answered 05 Jul '18, 08:57 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,652
×832
×167
×81

question asked: 15 Feb '16, 11:59

question was seen: 2,981 times

last updated: 05 Jul '18, 08:57