Dados dos enteros positivos N y K , la tarea es verificar si el entero N dado puede expresarse como el producto de K enteros consecutivos o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: N = 210, K = 3
Salida: Sí
Explicación: 210 se puede expresar como 5 * 6 * 7.Entrada: N = 780, K =4
Salida: No
Enfoque: el problema dado se puede resolver utilizando la técnica de ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Inicialice dos enteros, digamos Kthroot y product , para almacenar la K -ésima raíz del entero N y el producto de K enteros consecutivos respectivamente.
- Almacene el producto de números enteros en el rango [1, K] en la variable producto .
- De lo contrario, itere sobre el rango [2, Kthroot] y realice los siguientes pasos:
- Si el valor del producto es igual a N , imprima «Sí» y salga del bucle .
- Actualice el valor del producto como (producto*(i + K – 1)) / (i – 1) .
- Después de completar los pasos anteriores, si ninguno de los casos anteriores satisface, imprima «No» , ya que N no se puede expresar como el producto de K enteros consecutivos.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if N can be expressed
// as the product of K consecutive integers
string checkPro(int n, int k)
{
double exp = 1.0 / k;
// Stores the K-th root of N
int KthRoot = (int)pow(n, exp);
// Stores the product of K
// consecutive integers
int product = 1;
// Traverse over the range [1, K]
for(int i = 1; i < k + 1; i++)
{
// Update the product
product = product * i;
}
// If product is N, then return "Yes"
if (product == n)
return "Yes";
else
{
// Otherwise, traverse over
// the range [2, Kthroot]
for(int j = 2; j < KthRoot + 1; j++)
{
// Update the value of product
product = product * (j + k - 1);
product = product / (j - 1);
// If product is equal to N
if (product == n)
return "Yes";
}
}
// Otherwise, return "No"
return "No";
}
// Driver code
int main()
{
int N = 210;
int K = 3;
cout << checkPro(N, K);
return 0;
}
// This code is contributed by avijitmondal1998
Java
// Java program for the above approach
public class GFG {
// Function to check if N can be expressed
// as the product of K consecutive integers
static String checkPro(int n, int k){
double exp = 1.0 / k ;
// Stores the K-th root of N
int KthRoot = (int)Math.pow(n, exp);
// Stores the product of K
// consecutive integers
int product = 1 ;
// Traverse over the range [1, K]
for (int i = 1; i < k + 1; i++){
// Update the product
product = product * i;
}
// If product is N, then return "Yes"
if(product == n)
return "Yes";
else {
// Otherwise, traverse over
// the range [2, Kthroot]
for (int j = 2; j < KthRoot + 1; j++) {
// Update the value of product
product = product * (j + k - 1) ;
product = product / (j - 1) ;
// If product is equal to N
if(product == n)
return "Yes" ;
}
}
// Otherwise, return "No"
return "No" ;
}
// Driver Code
public static void main (String[] args) {
int N = 210;
int K = 3;
System.out.println(checkPro(N, K));
}
}
// This code is contributed by AnkThon
Python3
# Python3 program for the above approach
# Function to check if N can be expressed
# as the product of K consecutive integers
def checkPro(n, k):
# Stores the K-th root of N
KthRoot = int(n**(1 / k))
# Stores the product of K
# consecutive integers
product = 1
# Traverse over the range [1, K]
for i in range(1, k + 1):
# Update the product
product = product * i
print(product)
# If product is N, then return "Yes"
if(product == N):
return ("Yes")
# Otherwise, traverse over
# the range [2, Kthroot]
for i in range(2, KthRoot + 1):
# Update the value of product
product = product*(i + k-1)
product = product/(i - 1)
print(product)
# If product is equal to N
if(product == N):
return ("Yes")
# Otherwise, return "No"
return ("No")
# Driver Code
N = 210
K = 3
# Function Call
print(checkPro(N, K))
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if N can be expressed
// as the product of K consecutive integers
static string checkPro(int n, int k)
{
double exp = 1.0 / k ;
// Stores the K-th root of N
int KthRoot = (int)Math.Pow(n, exp);
// Stores the product of K
// consecutive integers
int product = 1 ;
// Traverse over the range [1, K]
for(int i = 1; i < k + 1; i++)
{
// Update the product
product = product * i;
}
// If product is N, then return "Yes"
if (product == n)
return "Yes";
else
{
// Otherwise, traverse over
// the range [2, Kthroot]
for(int j = 2; j < KthRoot + 1; j++)
{
// Update the value of product
product = product * (j + k - 1);
product = product / (j - 1);
// If product is equal to N
if (product == n)
return "Yes";
}
}
// Otherwise, return "No"
return "No";
}
// Driver Code
static public void Main()
{
int N = 210;
int K = 3;
Console.WriteLine(checkPro(N, K));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program for the above approach
// Function to check if N can be expressed
// as the product of K consecutive integers
function checkPro(n , k) {
var exp = 1.0 / k;
// Stores the K-th root of N
var KthRoot = parseInt( Math.pow(n, exp));
// Stores the product of K
// consecutive integers
var product = 1;
// Traverse over the range [1, K]
for (i = 1; i < k + 1; i++) {
// Update the product
product = product * i;
}
// If product is N, then return "Yes"
if (product == n)
return "Yes";
else {
// Otherwise, traverse over
// the range [2, Kthroot]
for (j = 2; j < KthRoot + 1; j++) {
// Update the value of product
product = product * (j + k - 1);
product = product / (j - 1);
// If product is equal to N
if (product == n)
return "Yes";
}
}
// Otherwise, return "No"
return "No";
}
// Driver Code
var N = 210;
var K = 3;
document.write(checkPro(N, K));
// This code contributed by Rajput-Ji
</script>
Producción:
Yes
Complejidad de Tiempo: O(K + N (1/K) )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA