Degree of Polynomial : DPOLY | CodeChef Solution

Problem

In mathematics, the degree of polynomials in one variable is the highest power of the variable in the algebraic expression with non-zero coefficient.

Chef has a polynomial in one variable x with N terms. The polynomial looks like A_0\cdot x^0 + A_1\cdot x^1 + \ldots + A_{N-2}\cdot x^{N-2} + A_{N-1}\cdot x^{N-1}A0​⋅x0+A1​⋅x1+…+AN−2​⋅xN−2+AN−1​⋅xN−1 where A_{i-1}Ai−1​ denotes the coefficient of the i^{th}ith term x^{i-1}xi−1 for all (1\le i\le N)(1≤i≤N).

Find the degree of the polynomial.

Note: It is guaranteed that there exists at least one term with non-zero coefficient.

Please Share this article...

Input Format

• First line will contain T, number of test cases. Then the test cases follow.
• First line of each test case contains of a single integer N - the number of terms in the polynomial.
• Second line of each test case contains of N space-separated integers - the i^th integer A_i-1 corresponds to the coefficient of x^i-1.

Output Format

For each test case, output in a single line, the degree of the polynomial.

Constraints

Sample

Input

4

1

5

2

-3 3

3

0 0 5

4

1 2 4 0

Output

0

1

2

2

Explanation

Test case 1: There is only one term x^0x0 with coefficient 5. Thus, we are given a constant polynomial and the degree is 0.

Test case 2: The polynomial is -3\cdot x^0 + 3\cdot x^1 = -3 + 3\cdot x−3⋅x0+3⋅x1=−3+3⋅x. Thus, the highest power of x with non-zero coefficient is 1.

Test case 3: The polynomial is 0\cdot x^0 + 0\cdot x^1 + 5\cdot x^2= 0+0 + 5\cdot x^20⋅x0+0⋅x1+5⋅x2=0+0+5⋅x2. Thus, the highest power of xwith non-zero coefficient is 2.

Test case 4: The polynomial is 1\cdot x^0 + 2\cdot x^1+ 4\cdot x^2 + 0\cdot x^3= 1 + 2\cdot x + 4\cdot x^21⋅x0+2⋅x1+4⋅x2+0⋅x3=1+2⋅x+4⋅x2. Thus, the highest power of x with non-zero coefficient is 2.

Solution

#include <bits/stdc++.h>
using namespace std;


// Solution from : Code Radius [ https://radiuscode.blogspot.com/ ]

int main() {
 int a,t;
    cin>>t;
    for(a=0;a<t;a++)
    {
        int n,a[1000],i;
        cin>>n;
        for(i=0;i<n;i++)
        {
            cin>>a[i];
        }
        for(i=n-1;i>=0;i--)
        {
            if(a[i]!=0)
            {
                break;
            }
        }
        cout<<i<<endl;
        
    }
 return 0;

}

Please First Try to Solve Problem by Yourself.