Engineer bro!

Sun Oct 31 2021 (4 weeks ago)

Engineer by mistake!

I am a software engineer by passion

Solving a basic number theory problem with c++

You are given two numbers, D&ND \& N. You have to find sum(N)sum(N) applied DD times.

(TOC generated by @dsabyte)

Problem description

Yesterday, puppy Tuzik learned a magically efficient method to find the sum of the integers from 11 to NN. He denotes it as sum(N)sum(N). But today, like a true explorer, he defined his own new function: sum(D,N)sum(D, N), which means the operation sum applied DD times: the first time to NN and each subsequent time to the result of the previous operation.

For example, if D=2D = 2 and N=3N = 3, then sum(2,3)sum(2, 3) equals to sum(sum(3))=sum(1+2+3)=sum(6)=21sum(sum(3)) = sum(1 + 2 + 3) = sum(6) = 21.

Tuzik wants to calculate some values of the sum(D,N)sum(D, N) function. Will you help him with that?

Input

The first line contains a single integer T, the number of test cases. Each test case is described by a single line containing two integers D and N.

Output

For each test case, output one integer on a separate line.

Constraints

  • 1T161 ≤ T ≤ 16

  • 1D,N41 ≤ D, N ≤ 4

Sample Input 1

2
1 4
2 3

Sample Output 1

10
21

Explanation

The problem will be simple if we just have to calculate sum(N)sum(N) because from basic mathematics we already know the formula. The Sum of numbers from 11 to NN is n(n+1)2\frac{n*(n+1)}{2}.

Using the above formula, we can find sum of the numbers from 11 to NN in just O(1)O(1) time.

But, here we just don't have to calculate sum(n)sum(n), we have to repeat it DD times.

Let's dry run one of the above examples, D=2,N=3D=2, N=3.

Iteration Function call Numbers Result
1 sum(3)sum(3) 1+2+31+2+3 66
2 sum(sum(3))=sum(6)sum(sum(3)) = sum(6) 1+2+3+4+5+61+2+3+4+5+6 2121

Here, we can see that we just need to call native sum(n)sum(n) function DD times with the initial value of NN.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int d, n;
        cin >> d >> n;

        int ans = n; // initialize and as n
        for (int i = 0; i < d; i++) {
            ans = (ans * (ans + 1)) / 2;
        }

        cout << ans << endl;
    }
    return 0;
}

Complexity

  • Time - O(dt)O(d*t), O(d)O(d) per test case

  • Space - O(1)O(1)

Want to try the solution

Thank You ❤️

cppmathnumber theorysum

Comments (0)

Discussions (0)


© 2021 dsabyte. All rights reserved