We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #101: Optimum polynomial

Project Euler #101: Optimum polynomial

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 101 from projecteuler.net

If we are presented with the first terms of a sequence it is impossible to say with certainty the value of the next term, as there are infinitely many polynomial functions that can model the sequence.

As an example, let us consider the sequence of cube numbers. This is defined by the generating function,

Suppose we were only given the first two terms of this sequence. Working on the principle that "simple is best" we should assume a linear relationship and predict the next term to be 15 (common difference 7). Even if we were presented with the first three terms, by the same principle of simplicity, a quadratic relationship should be assumed.

We shall define to be the term of the optimum polynomial generating function for the first terms of a sequence. It should be clear that will accurately generate the terms of the sequence for , and potentially the first incorrect term (FIT) will be ; in which case we shall call it a bad OP (BOP).

As a basis, if we were only given the first term of sequence, it would be most sensible to assume constancy; that is, for .

Hence we obtain the following OPs for the cubic sequence:

Clearly no BOPs exist for .

You are given the polynomial. Find all FITs of it modulo .

Input Format

First line contains a single integer . The second line contains integer - the coefficients of the polynomial :

Constraints

Output Format

Output one line with integers which are FITs modulo .

Sample Input

3
0 0 0 1

Sample Output

1 15 58

Author

MarcusAndrews

Difficulty

Medium

Max Score

100

Submitted By

422

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy