6
\$\begingroup\$

You are given a polynomial of degree n. The polynomial is of the form

P(x) = an · xn + an-1 · xn-1 + … + a0

where the ai‘s are the coefficients. Given an integer x, write a program that will evaluate P(x).

You are provided with a function named power( ) that takes two positive integers x and y and returns xy. If y is 0, the function returns 1.

The prototype of this function is

int power(int x, int y);

INPUT:

  • Line 1 contains the integers n and x separated by whitespace.
  • Line 2 contains the coefficients an, an-1, …, a0 separated by whitespace.

OUTPUT:

A single integer which is P(x).

CONSTRAINTS:

The inputs will satisfy the following properties. It is not necessary to validate the inputs.

1 <= n <= 10
1 <= x <= 10
0 <= ai <=10

My code

#include<stdio.h>

int power(int x, int y);

int main()
{

int n,x,a[11],i; unsigned long long int sum=1;
scanf("%d%d",&n,&x);
if(n<1 || n>10) return 0;
if(x<1 || x>10) return 0;



for(i=0;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]< 0 || a[i]>10) return 0;
}
for(i=0;i<n;i++)
{

sum+=power(x,n-i)*a[i];
}
printf("%llu",sum);

    return 0;
}



int power(int x, int y)
 {
   int result = x,i;

   if(y == 0) return 1;
   if(x < 0 || y < 0) return 0;

   for(i = 1; i < y; ++i)
   result *= x;

   return result;
}
\$\endgroup\$
1

3 Answers 3

4
\$\begingroup\$
  1. Recommend a uniform and more indented style. E.g.

    for(i=0;i<n;i++)
    {
        sum+=power(x,n-i)*a[i];
    }
    
  2. Both a[11] and if(... n>10) rely on the same value. Also to avoid undocumented magic numbers, consider the following (also the same for x and a[]):

    #define n_MAX (10)
    #define n_MIN (0)
    int a[n_MAX + 1];
    if(n<n_MIN || n>n_MAX) return 0;
    
  3. unsigned long long int sum serves little value in protecting against numbers larger than INT_MAX as power() is the most likely candidate to overflow. (Strictly speaking, it is not even known that LLONG_MAX is greater than INT_MAX.) So if you want a larger range, re-write power() as unsigned long long power(int x, int y), otherwise leaving sum as int is OK.

    Else suggest for marginal range improvement:

    sum += (unsigned long long) power(x,n-i) * a[i];
    
  4. BTW: should not it be:

    unsigned long long int sum = 0;  //( 0 not 1)
    
  5. Note: Stated objective says "It is not necessary to validate the inputs.". Still I like the testing you have done. Possible that the final reviewer (teacher?) may object to unneeded code. Could wrap in an #if DEBUG macro...

  6. Faster way to do power()

  7. See no reason for x<0 test in if(x < 0 || y < 0) return 0;. Could be

    if (y < 0) return 0;
    
  8. Do power() with unsigned rather than int as " function named power( ) that takes two positive integers x and y".

  9. @Constructor comment leads to an excellent suggestion. Calculate sum with a loop that does the below. No need for a power function. Running sum can be unsigned long long and code gets great range. Its faster & simple.

    // sum = (((a[n]*x + a[n-1])*x + a[n-2])*x + .... )*x + a[0];
    
    // Something like
    unsigned long long sum = 0;
    for (int i=n; i>=0; i--) {
      sum *= x;
      sum += a[i];
    }
    
  10. Lastly, even the array a is not needed:

    #include<stdio.h>
    int main() {
      int n;
      unsigned x, a;
      unsigned long long sum = 0;
      scanf("%d%u", &n, &x);
      while (n-- >= 0) {
        scanf("%u", &a);
        sum *= x;
        sum += a;
      }
      printf("%llu", sum);
      return 0;
    }
    
\$\endgroup\$
0
2
\$\begingroup\$

You can solve this problem without using a power function. However, you can optimize your POW(x,y) to O(logn) using Divide and conquer approach,

 A^n = A^(n/2) * A^(n/2) if n is even
     = A^(n/2) * A^(n/2) * A if n is odd
int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}
\$\endgroup\$
2
\$\begingroup\$

A few suggestions:

  • Whitespace (formatting) makes the code more readable: be especially careful with indentation; and don't waste vertical space with too many empty lines because you want to see the whole function on your limited-size screen)
  • Don't declare variables before you assign a value to them. Declaring all your variables at the top of the function was necessary in old-style C but is no longer required.
  • You don't need the a[11] array.
  • You don't need to write the power function because the specifications say, "You are provided with a function ..."
  • You don't need to validate your input (normally you should; but the specifications which you quoted for this problem say that you needn't: and you should usually read and obey the specifications).
  • The biggest possible value of xn is 1010 for which you'll need a more-than-32-bit integer:
    • Is this is a trick question, or an mistake by whoever wrote the specs?
    • Is the power function (which returns int) implicitly working with 64-bit integers?
    • Do you need to define your own version of the power function using int64_t?
  • If you want to declare an explicitly-64-bit integer it's called int64_t.

If your compiler doesn't support 64-bit arithmetic you can implement it yourself but that makes the code a bit more complicated.

The following is FYI my attempt to do this problem in minimum/cleanest lines of code:

int main()
{
    // Line 1 contains the integers n and x separated by whitespace.
    int n, x;
    scanf("%d%d", &n, &x);

    int64_t sum = 0;
    for (int i = 0; i <= n; ++i) {
        // Line 2 contains the coefficients an, an-1, ..., a0 separated by whitespace.
        int a;
        scanf("%d", &a);
        sum += a * power(x, n - i);
    }

    // Use PRId64 defined in <inttypes.h> to print int64_t
    // https://stackoverflow.com/a/9225648/49942
    printf("%" PRId64, sum);
    return 0;
}

You may agree that my version is more readable than yours; partly because it's shorter.

I added comments which describe the problem being solved (by copying them from the specification).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.