Given three positive integers N, R, and A and a polynomial P(X) of degree N, P(i) = 1 for 1 ? i ? N and the value of P(N + 1) is A, the task is to find the value of the P(N + R).
Examples:
Input: N = 1, R = 3, A = 2
Output: 4
Explanation:
The equation of the given polynomial is P(x) = x. Therefore, the value of P(N + R) = P(4) = 4.Input: N = 2, R = 3, A = 1
Output: 1
Approach: The given problem can be solved by finding the expression of the given polynomial P(X) and then calculate the value of P(N + R). The general form of a polynomial with degree N is:
P(x) = k * (x – x1) * (x – x2) * (x – x3) * … *(x – xn) + c
where x1, x2, x3, …, xn are the roots P(x) where k and c are arbitrary constants.
Consider F(x) be another polynomial of degree N such that
F(x) = P(x) + c — (1)Now, if c = -1, F(x) = 0 since P(x) = 1 for x ? [1, N].
? F(x) has N roots which are equal to 1, 2, 3, …, N.
Therefore, F(x) = k * (x – 1) * (x – 2) * … * (x – N), for all c = -1.Rearranging terms in equation (1),
P(x) = F(x) – c
P(x) = k * (x – 1) * (x – 2) * … *(x – N) + 1 — (2)Putting x = N + 1 in equation (2),
k = (a – 1) / N!Therefore, P(x) = ((a – 1)/N!) * (x – 1) * (x – 2) * … *(x – N) + 1 — (3)
Therefore, the idea is to substitute the value of (N + R) in equation (3) and print the value of the expression as the result. Follow the steps below to solve the problem:
- Initialize a variable, say ans, as the value of (A – 1) / N!.
- Iterate over the range [1, N] using the variable i and update the value of ans as ans * (N + R – i).
- After completing the above steps, print the value of (ans + 1) as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h>using namespace std;// Function to calculate// factorial of Nint fact(int n){ // Base Case if (n == 1 || n == 0) return 1; // Otherwise, recursively // calculate the factorial else return n * fact(n - 1);}// Function to find the value of// P(n + r) for polynomial P(X)int findValue(int n, int r, int a){ // Stores the value of k int k = (a - 1) / fact(n); // Store the required answer int answer = k; // Iterate in the range [1, N] and // multiply (n + r - i) with answer for(int i = 1; i < n + 1; i++) answer = answer * (n + r - i); // Add the constant value C as 1 answer = answer + 1; // Return the result return answer;}// Driver Codeint main(){ int N = 1; int A = 2; int R = 3; cout << (findValue(N, R, A)); return 0;}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approach import java.util.*;class GFG{ // Function to calculate// factorial of Nstatic int fact(int n){ // Base Case if (n == 1 || n == 0) return 1; // Otherwise, recursively // calculate the factorial else return n * fact(n - 1);}// Function to find the value of// P(n + r) for polynomial P(X)static int findValue(int n, int r, int a){ // Stores the value of k int k = (a - 1) / fact(n); // Store the required answer int answer = k; // Iterate in the range [1, N] and // multiply (n + r - i) with answer for(int i = 1; i < n + 1; i++) answer = answer * (n + r - i); // Add the constant value C as 1 answer = answer + 1; // Return the result return answer;}// Driver Codepublic static void main(String args[]){ int N = 1; int A = 2; int R = 3; System.out.print(findValue(N, R, A));}}// This code is contributed by SURENDRA_GANGWAR. |
Python3
# Python program for the above approach# Function to calculate# factorial of Ndef fact(n): # Base Case if n == 1 or n == 0: return 1 # Otherwise, recursively # calculate the factorial else: return n * fact(n-1)# Function to find the value of# P(n + r) for polynomial P(X)def findValue(n, r, a): # Stores the value of k k = (a-1) // fact(n) # Store the required answer answer = k # Iterate in the range [1, N] and # multiply (n + r - i) with answer for i in range(1, n + 1): answer = answer*(n + r-i) # Add the constant value C as 1 answer = answer + 1 # Return the result return answer# Driver CodeN = 1A = 2R = 3print(findValue(N, R, A)) |
C#
// C# program for the above approachusing System;class GFG{// Function to calculate// factorial of Nstatic int fact(int n){ // Base Case if (n == 1 || n == 0) return 1; // Otherwise, recursively // calculate the factorial else return n * fact(n - 1);}// Function to find the value of// P(n + r) for polynomial P(X)static int findValue(int n, int r, int a){ // Stores the value of k int k = (a - 1) / fact(n); // Store the required answer int answer = k; // Iterate in the range [1, N] and // multiply (n + r - i) with answer for(int i = 1; i < n + 1; i++) answer = answer * (n + r - i); // Add the constant value C as 1 answer = answer + 1; // Return the result return answer;}// Driver Codestatic public void Main(){ int N = 1; int A = 2; int R = 3; Console.Write((findValue(N, R, A)));}}// This code is contributed by code_hunt |
Javascript
<script>// JavaScript program to implement// the above approach// Function to calculate// factorial of Nfunction fact(n){ // Base Case if (n == 1 || n == 0) return 1; // Otherwise, recursively // calculate the factorial else return n * fact(n - 1);} // Function to find the value of// P(n + r) for polynomial P(X)function findValue(n, r, a){ // Stores the value of k let k = (a - 1) / fact(n); // Store the required answer let answer = k; // Iterate in the range [1, N] and // multiply (n + r - i) with answer for(let i = 1; i < n + 1; i++) answer = answer * (n + r - i); // Add the constant value C as 1 answer = answer + 1; // Return the result return answer;}// Driver code let N = 1; let A = 2; let R = 3; document.write(findValue(N, R, A)); // This code is contributed by code_hunt.</script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
