You are not logged in. Please login at to post your questions!


PPSUM - Editorial

Problem Link:


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




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.


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[i] = sumN[i-1] + i;
int main() {
    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)$.

Similar Problems



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".

asked 15 Feb '16, 11:59

ma5termind's gravatar image

accept rate: 11%

edited 22 Feb '16, 00:36

admin's gravatar image

0★admin ♦♦

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

rajeeb_7341's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 15 Feb '16, 11:59

question was seen: 2,981 times

last updated: 05 Jul '18, 08:57