Dados tres enteros positivos N , R y A y un polinomio P(X) de grado N , P(i) = 1 para 1 ≤ i ≤ N y el valor de P(N + 1) es A , la tarea es encuentra el valor de P(N + R) .
Ejemplos:
Entrada: N = 1, R = 3, A = 2
Salida: 4
Explicación:
La ecuación del polinomio dado es P(x) = x. Por lo tanto, el valor de P(N + R) = P(4) = 4.Entrada: N = 2, R = 3, A = 1
Salida: 1
Enfoque: El problema dado se puede resolver encontrando la expresión del polinomio dado P(X) y luego calculando el valor de P(N + R) . La forma general de un polinomio de grado N es:
P(x) = k * (x – x 1 ) * (x – x 2 ) * (x – x 3 ) * … *(x – x n ) + c
donde x 1 , x 2 , x 3 , …, x n son las raíces P(x) donde k y c son constantes arbitrarias.
Sea F(x) otro polinomio de grado N tal que
F(x) = P(x) + c — (1)Ahora, si c = -1, F(x) = 0 ya que P(x) = 1 para x ∈ [1, N].
⇒ F(x) tiene N raíces que son iguales a 1, 2, 3, …, N.
Por lo tanto, F(x) = k * (x – 1) * (x – 2) * … * (x – N) , para todo c = -1.Reordenando términos en la ecuación (1),
P(x) = F(x) – c
P(x) = k * (x – 1) * (x – 2) * … *(x – N) + 1 — (2 )Poniendo x = N + 1 en la ecuación (2),
k = (a – 1) / N!Por lo tanto, P(x) = ((a – 1)/N!) * (x – 1) * (x – 2) * … *(x – N) + 1 — (3)
Por lo tanto, la idea es sustituir el valor de (N + R) en la ecuación (3) e imprimir el valor de la expresión como resultado. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans , como el valor de (A – 1) / N! .
- Iterar sobre el rango [1, N] usando la variable i y actualizar el valor de ans como ans * (N + R – i) .
- Después de completar los pasos anteriores, imprima el valor de (ans + 1) como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// factorial of N
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)
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 Code
int 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 N
static 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 Code
public 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 N def 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 Code N = 1 A = 2 R = 3 print(findValue(N, R, A))
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate
// factorial of N
static 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 Code
static 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 N
function 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
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por santhoshcharan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA