Given a sequence with some of its term, we need to calculate next K term of this sequence. It is given that sequence is generated by some polynomial, however complex that polynomial can be. Notice polynomial is an expression of the following form:
P(x) = a0 + a1 x +a2 x^2 + a3 x^3 …….. + an x^n
The given sequence can always be described by a number of polynomials, among these polynomial we need to find polynomial with lowest degree and generate next terms using this polynomial only.
Examples:
If given sequence is 1, 2, 3, 4, 5 then its next term will be 6, 7, 8, etc and this correspond to a trivial polynomial. If given sequence is 1, 4, 7, 10 then its next term will be 13, 16, etc.
We can solve this problem using a technique called difference of differences method, which is derivable from lagrange polynomial.
The technique is simple, we take the difference between the consecutive terms, if difference are equal then we stop and build up next term of the sequence otherwise we again take the difference between these differences until they become constant.
The technique is explained in below diagram with an example, given sequence is 8, 11, 16, 23 and we are suppose to find next 3 terms of this sequence.
In below, code same technique is implemented, first we loop until we get a constant difference keeping first number of each difference sequence in a separate vector for rebuilding the sequence again. Then we add K instance of same constant difference to our array for generating new K term of sequence and we follow same procedure in reverse order to rebuild the sequence.
See the below code for a better understanding.
C++
// C++ code to generate next terms of a given polynomial// sequence#include <bits/stdc++.h>using namespace std;// method to print next terms term of sequencevoid nextTermsInSequence(int sequence[], int N, int terms){ int diff[N + terms]; // first copy the sequence itself into diff array for (int i = 0; i < N; i++) diff[i] = sequence[i]; bool more = false; vector<int> first; int len = N; // loop until one difference remains or all // difference become constant while (len > 1) { // keeping the first term of sequence for // later rebuilding first.push_back(diff[0]); len--; // converting the difference to difference // of differences for (int i = 0; i < len; i++) diff[i] = diff[i + 1] - diff[i]; // checking if all difference values are // same or not int i; for (i = 1; i < len; i++) if (diff[i] != diff[i - 1]) break; // If some difference values were not same if (i != len) break; } int iteration = N - len; // padding terms instance of constant difference // at the end of array for (int i = len; i < len + terms; i++) diff[i] = diff[i - 1]; len += terms; // iterating to get actual sequence back for (int i = 0; i < iteration; i++) { len++; // shifting all difference by one place for (int j = len - 1; j > 0; j--) diff[j] = diff[j - 1]; // copying actual first element diff[0] = first[first.size() - i - 1]; // converting difference of differences to // difference array for (int j = 1; j < len; j++) diff[j] = diff[j - 1] + diff[j]; } // printing the result for (int i = 0; i < len; i++) cout << diff[i] << " "; cout << endl;}// Driver code to test above methodint main(){ int sequence[] = {8, 11, 16, 23}; int N = sizeof(sequence) / sizeof(int); int terms = 3; nextTermsInSequence(sequence, N, terms); return 0;} |
Java
// Java code to generate next terms // of a given polynomial sequenceimport java.util.*; class GFG{ // Method to print next terms term of sequencestatic void nextTermsInSequence(int []sequence, int N, int terms){ int []diff = new int[N + terms]; // First copy the sequence itself // into diff array for(int i = 0; i < N; i++) diff[i] = sequence[i]; //bool more = false; ArrayList<Object> first = new ArrayList<Object>(); int len = N; // Loop until one difference remains // or all difference become constant while (len > 1) { // Keeping the first term of // sequence for later rebuilding first.add(diff[0]); len--; // Converting the difference to // difference of differences for(int i = 0; i < len; i++) diff[i] = diff[i + 1] - diff[i]; // Checking if all difference values // are same or not int j; for(j = 1; j < len; j++) if (diff[j] != diff[j - 1]) break; // If some difference values // were not same if (j != len) break; } int iteration = N - len; // Padding terms instance of constant // difference at the end of array for(int i = len; i < len + terms; i++) diff[i] = diff[i - 1]; len += terms; // Iterating to get actual sequence back for(int i = 0; i < iteration; i++) { len++; // Shifting all difference by one place for(int j = len - 1; j > 0; j--) diff[j] = diff[j - 1]; // Copying actual first element diff[0] = (int)first.get(first.size() - i - 1); // Converting difference of differences // to difference array for(int j = 1; j < len; j++) diff[j] = diff[j - 1] + diff[j]; } // Printing the result for(int i = 0; i < len; i++) { System.out.print(diff[i] + " "); } System.out.println();} // Driver Codepublic static void main(String[] args){ int []sequence = { 8, 11, 16, 23 }; int N = sequence.length; int terms = 3; nextTermsInSequence(sequence, N, terms);}} // This code is contributed by pratham76 |
Python3
# Python3 code to generate next terms# of a given polynomial sequence# Method to print next terms term of sequencedef nextTermsInSequence(sequence, N, terms): diff = [0] * (N + terms) # First copy the sequence itself # into diff array for i in range(N): diff[i] = sequence[i] more = False first = [] length = N # Loop until one difference remains # or all difference become constant while (length > 1): # Keeping the first term of sequence # for later rebuilding first.append(diff[0]) length -= 1 # Converting the difference to difference # of differences for i in range(length): diff[i] = diff[i + 1] - diff[i] # Checking if all difference values are # same or not for i in range(1, length): if (diff[i] != diff[i - 1]): break # If some difference values # were not same if (i != length): break iteration = N - length # Padding terms instance of constant # difference at the end of array for i in range(length, length + terms): diff[i] = diff[i - 1] length += terms # Iterating to get actual sequence back for i in range(iteration): length += 1 # Shifting all difference by one place for j in range(length - 1, -1, -1): diff[j] = diff[j - 1] # Copying actual first element diff[0] = first[len(first) - i - 1] # Converting difference of differences to # difference array for j in range(1, length): diff[j] = diff[j - 1] + diff[j] # Printing the result for i in range(length): print(diff[i], end = " ") print ()# Driver code if __name__ == "__main__": sequence = [ 8, 11, 16, 23 ] N = len(sequence) terms = 3 nextTermsInSequence(sequence, N, terms)# This code is contributed by chitranayal |
C#
// C# code to generate next terms // of a given polynomial sequenceusing System;using System.Collections; class GFG{ // Method to print next terms term of sequencestatic void nextTermsInSequence(int []sequence, int N, int terms){ int []diff = new int[N + terms]; // First copy the sequence itself // into diff array for(int i = 0; i < N; i++) diff[i] = sequence[i]; //bool more = false; ArrayList first = new ArrayList(); int len = N; // Loop until one difference remains // or all difference become constant while (len > 1) { // Keeping the first term of // sequence for later rebuilding first.Add(diff[0]); len--; // Converting the difference to // difference of differences for(int i = 0; i < len; i++) diff[i] = diff[i + 1] - diff[i]; // Checking if all difference values // are same or not int j; for(j = 1; j < len; j++) if (diff[j] != diff[j - 1]) break; // If some difference values // were not same if (j != len) break; } int iteration = N - len; // Padding terms instance of constant // difference at the end of array for(int i = len; i < len + terms; i++) diff[i] = diff[i - 1]; len += terms; // Iterating to get actual sequence back for(int i = 0; i < iteration; i++) { len++; // Shifting all difference by one place for(int j = len - 1; j > 0; j--) diff[j] = diff[j - 1]; // Copying actual first element diff[0] = (int)first[first.Count - i - 1]; // Converting difference of differences // to difference array for(int j = 1; j < len; j++) diff[j] = diff[j - 1] + diff[j]; } // Printing the result for(int i = 0; i < len; i++) { Console.Write(diff[i] + " "); } Console.Write("\n");}// Driver Codepublic static void Main(string[] args){ int []sequence = { 8, 11, 16, 23 }; int N = sequence.Length; int terms = 3; nextTermsInSequence(sequence, N, terms);}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript code to generate next terms// of a given polynomial sequence // Method to print next terms term of sequence function nextTermsInSequence(sequence, N,terms) { let diff = new Array(N + terms); // First copy the sequence itself // into diff array for(let i = 0; i < N; i++) diff[i] = sequence[i]; //bool more = false; let first=[]; let len = N; // Loop until one difference remains // or all difference become constant while (len > 1) { // Keeping the first term of // sequence for later rebuilding first.push(diff[0]); len--; // Converting the difference to // difference of differences for(let i = 0; i < len; i++) diff[i] = diff[i + 1] - diff[i]; // Checking if all difference values // are same or not let j; for(j = 1; j < len; j++) if (diff[j] != diff[j - 1]) break; // If some difference values // were not same if (j != len) break; } let iteration = N - len; // Padding terms instance of constant // difference at the end of array for(let i = len; i < len + terms; i++) diff[i] = diff[i - 1]; len += terms; // Iterating to get actual sequence back for(let i = 0; i < iteration; i++) { len++; // Shifting all difference by one place for(let j = len - 1; j > 0; j--) diff[j] = diff[j - 1]; // Copying actual first element diff[0] = first[first.length - i - 1]; // Converting difference of differences // to difference array for(let j = 1; j < len; j++) diff[j] = diff[j - 1] + diff[j]; } // Printing the result for(let i = 0; i < len; i++) { document.write(diff[i] + " "); } document.write("<br>"); } // Driver Code let sequence=[8, 11, 16, 23]; let N = sequence.length; let terms = 3; nextTermsInSequence(sequence, N, terms); // This code is contributed by avanitrachhadiya2155 </script> |
Output
8 11 16 23 30 37 44
Time Complexity: O(N2+N*terms)
Auxiliary Space: O(N+terms)
This article is contributed by Utkarsh Trivedi. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
