Dado un arreglo arr[] de N enteros y un entero K, la tarea es encontrar un subarreglo de longitud K con una suma de elementos igual al factorial de cualquier número . Si no existe tal subarreglo, imprima » -1″ .
Ejemplos:
Entrada: arr[] = {23, 45, 2, 4, 6, 9, 3, 32}, K = 5
Salida: 2 4 6 9 3
Explicación:
Subarreglo {2, 4, 6, 9, 3} con suma 24 (= 4!) satisface la condición requerida.Entrada: arr[] = {23, 45, 2, 4, 6, 9, 3, 32}, K = 3
Salida: -1
Explicación:
No existe tal subarreglo de longitud K (= 3).
Enfoque ingenuo: el enfoque más simple para resolver el problema es calcular la suma de todos los subarreglos de longitud K y verificar si alguna de esas sumas es factorial de cualquier número . Si se encuentra que es cierto para cualquier subarreglo, imprima ese subarreglo. De lo contrario, imprima «-1» .
Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar la técnica de ventana deslizante para calcular la suma de todos los subarreglos de longitud K y luego verificar si la suma es un factorial o no . A continuación se muestran los pasos:
- Calcule la suma de los primeros elementos de la array K y almacene la suma en una variable, digamos sum .
- Luego, recorra la array restante y siga actualizando sum para obtener la suma del subarreglo actual de tamaño K restando el primer elemento del subarreglo anterior y sumando el elemento del arreglo actual.
- Para verificar si la suma es un factorial de un número o no, divide la suma por 2, 3, y así sucesivamente hasta que no se pueda dividir más. Si el número se reduce a 1, la suma es el factorial de un número.
- Si la suma en el paso anterior es un factorial de un número, almacene el índice inicial y final de ese subarreglo para imprimir el subarreglo.
- Después de completar los pasos anteriores, si no se encuentra tal subarreglo, imprima «-1» . De lo contrario, imprima el subarreglo cuyos índices inicial y final están almacenados.
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 check if a number
// is factorial of a number or not
int isFactorial(int n)
{
int i = 2;
while (n != 1) {
// If n is not a factorial
if (n % i != 0) {
return 0;
}
n /= i;
i++;
}
return i - 1;
}
// Function to return the index of
// the valid subarray
pair<int, int> sumFactorial(
vector<int> arr, int K)
{
int i, sum = 0, ans;
// Calculate the sum of
// first subarray of length K
for (i = 0; i < K; i++) {
sum += arr[i];
}
// Check if sum is a factorial
// of any number or not
ans = isFactorial(sum);
// If sum of first K length subarray
// is factorial of a number
if (ans != 0) {
return make_pair(ans, 0);
}
// Find the number formed from the
// subarray which is a factorial
for (int j = i; j < arr.size(); j++) {
// Update sum of current subarray
sum += arr[j] - arr[j - K];
// Check if sum is a factorial
// of any number or not
ans = isFactorial(sum);
// If ans is true, then return
// index of the current subarray
if (ans != 0) {
return make_pair(ans,
j - K + 1);
}
}
// If the required subarray is
// not possible
return make_pair(-1, 0);
}
// Function to print the subarray whose
// sum is a factorial of any number
void printRes(pair<int, int> answer,
vector<int> arr, int K)
{
// If no such subarray exists
if (answer.first == -1) {
cout << -1 << endl;
}
// Otherwise
else {
int i = 0;
int j = answer.second;
// Iterate to print subarray
while (i < K) {
cout << arr[j] << " ";
i++;
j++;
}
}
}
// Driver Code
int main()
{
vector<int> arr
= { 23, 45, 2, 4,
6, 9, 3, 32 };
// Given sum K
int K = 5;
// Function Call
pair<int, int> answer
= sumFactorial(arr, K);
// Print the result
printRes(answer, arr, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import java.io.*;
class GFG{
// Pair class
public static class Pair
{
int x;
int y;
Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Function to check if a number
// is factorial of a number or not
static int isFactorial(int n)
{
int i = 2;
while (n != 1)
{
// If n is not a factorial
if (n % i != 0)
{
return 0;
}
n /= i;
i++;
}
return i - 1;
}
// Function to return the index of
// the valid subarray
static ArrayList<Pair> sumFactorial(int arr[],
int K)
{
ArrayList<Pair> pair = new ArrayList<>();
int i, sum = 0, ans;
// Calculate the sum of
// first subarray of length K
for(i = 0; i < K; i++)
{
sum += arr[i];
}
// Check if sum is a factorial
// of any number or not
ans = isFactorial(sum);
// If sum of first K length subarray
// is factorial of a number
if (ans != 0)
{
Pair p = new Pair(ans, 0);
pair.add(p);
return pair;
}
// Find the number formed from the
// subarray which is a factorial
for(int j = i; j < arr.length; j++)
{
// Update sum of current subarray
sum += arr[j] - arr[j - K];
// Check if sum is a factorial
// of any number or not
ans = isFactorial(sum);
// If ans is true, then return
// index of the current subarray
if (ans != 0)
{
Pair p = new Pair(ans, j - K + 1);
pair.add(p);
return pair;
}
}
// If the required subarray is
// not possible
Pair p = new Pair(-1, 0);
pair.add(p);
return pair;
}
// Function to print the subarray whose
// sum is a factorial of any number
static void printRes(ArrayList<Pair> answer,
int arr[], int K)
{
// If no such subarray exists
if (answer.get(0).x == -1)
{
// cout << -1 << endl;
System.out.println("-1");
}
// Otherwise
else
{
int i = 0;
int j = answer.get(0).y;
// Iterate to print subarray
while (i < K)
{
System.out.print(arr[j] + " ");
i++;
j++;
}
}
}
// Driver Code
public static void main(String args[])
{
// Given array arr[] and brr[]
int arr[] = { 23, 45, 2, 4,
6, 9, 3, 32 };
int K = 5;
ArrayList<Pair> answer = new ArrayList<>();
// Function call
answer = sumFactorial(arr,K);
// Print the result
printRes(answer, arr, K);
}
}
// This code is contributed by bikram2001jha
Python3
# Python3 program for the above approach # Function to check if a number # is factorial of a number or not def isFactorial(n): i = 2 while (n != 1): # If n is not a factorial if (n % i != 0): return 0 n = n // i i += 1 return i - 1 # Function to return the index of # the valid subarray def sumFactorial(arr, K): i, Sum = 0, 0 # Calculate the sum of # first subarray of length K while(i < K): Sum += arr[i] i += 1 # Check if sum is a factorial # of any number or not ans = isFactorial(Sum) # If sum of first K length subarray # is factorial of a number if (ans != 0): return (ans, 0) # Find the number formed from the # subarray which is a factorial for j in range(i, len(arr)): # Update sum of current subarray Sum = Sum + arr[j] - arr[j - K] # Check if sum is a factorial # of any number or not ans = isFactorial(Sum) # If ans is true, then return # index of the current subarray if (ans != 0): return (ans, j - K + 1) # If the required subarray is # not possible return (-1, 0) # Function to print the subarray whose # sum is a factorial of any number def printRes(answer, arr, K): # If no such subarray exists if (answer[0] == -1): print(-1) # Otherwise else: i = 0 j = answer[1] # Iterate to print subarray while (i < K): print(arr[j], end = " ") i += 1 j += 1 # Driver code arr = [ 23, 45, 2, 4, 6, 9, 3, 32 ] # Given sum K K = 5 # Function call answer = sumFactorial(arr, K) # Print the result printRes(answer, arr, K) # This code is contributed by divyeshrabadiya07
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Pair class
public class Pair
{
public int x;
public int y;
public Pair(int x, int y)
{
this.x = x;
this.y = y;
}
}
// Function to check if a number
// is factorial of a number or not
static int isFactorial(int n)
{
int i = 2;
while (n != 1)
{
// If n is not
// a factorial
if (n % i != 0)
{
return 0;
}
n /= i;
i++;
}
return i - 1;
}
// Function to return the index of
// the valid subarray
static List<Pair> sumFactorial(int []arr,
int K)
{
List<Pair> pair = new List<Pair>();
int i, sum = 0, ans;
// Calculate the sum of
// first subarray of length K
for(i = 0; i < K; i++)
{
sum += arr[i];
}
// Check if sum is a factorial
// of any number or not
ans = isFactorial(sum);
// If sum of first K length subarray
// is factorial of a number
if (ans != 0)
{
Pair p = new Pair(ans, 0);
pair.Add(p);
return pair;
}
// Find the number formed from the
// subarray which is a factorial
for(int j = i; j < arr.Length; j++)
{
// Update sum of current subarray
sum += arr[j] - arr[j - K];
// Check if sum is a factorial
// of any number or not
ans = isFactorial(sum);
// If ans is true, then return
// index of the current subarray
if (ans != 0)
{
Pair p = new Pair(ans, j - K + 1);
pair.Add(p);
return pair;
}
}
// If the required subarray is
// not possible
Pair p1 = new Pair(-1, 0);
pair.Add(p1);
return pair;
}
// Function to print the subarray whose
// sum is a factorial of any number
static void printRes(List<Pair> answer,
int []arr, int K)
{
// If no such subarray exists
if (answer[0].x == -1)
{
// cout << -1 << endl;
Console.WriteLine("-1");
}
// Otherwise
else
{
int i = 0;
int j = answer[0].y;
// Iterate to print subarray
while (i < K)
{
Console.Write(arr[j] + " ");
i++;
j++;
}
}
}
// Driver Code
public static void Main(String []args)
{
// Given array []arr and brr[]
int []arr = {23, 45, 2, 4,
6, 9, 3, 32};
int K = 5;
List<Pair> answer = new List<Pair>();
// Function call
answer = sumFactorial(arr, K);
// Print the result
printRes(answer, arr, K);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to check if a number
// is factorial of a number or not
function isFactorial(n)
{
let i = 2;
while (n != 1) {
// If n is not a factorial
if (n % i != 0) {
return 0;
}
n = parseInt(n / i, 10);
i++;
}
return i - 1;
}
// Function to return the index of
// the valid subarray
function sumFactorial(arr,K)
{
let i, sum = 0, ans;
// Calculate the sum of
// first subarray of length K
for (i = 0; i < K; i++) {
sum += arr[i];
}
// Check if sum is a factorial
// of any number or not
ans = isFactorial(sum);
// If sum of first K length subarray
// is factorial of a number
if (ans != 0) {
return [ans, 0];
}
// Find the number formed from the
// subarray which is a factorial
for (let j = i; j < arr.length; j++) {
// Update sum of current subarray
sum += arr[j] - arr[j - K];
// Check if sum is a factorial
// of any number or not
ans = isFactorial(sum);
// If ans is true, then return
// index of the current subarray
if (ans != 0) {
return [ans, j - K + 1];
}
}
// If the required subarray is
// not possible
return [-1, 0];
}
// Function to print the subarray whose
// sum is a factorial of any number
function printRes(answer,arr,K)
{
// If no such subarray exists
if (answer[0] == -1) {
document.write(-1);
}
// Otherwise
else {
let i = 0;
let j = answer[1];
// Iterate to print subarray
while (i < K) {
document.write(arr[j] + " ");
i++;
j++;
}
}
}
// Driver Code
let arr= [ 23, 45, 2, 4,
6, 9, 3, 32 ];
// Given sum K
let K = 5;
// Function Call
let answer= sumFactorial(arr, K);
// Print the result
printRes(answer, arr, K);
</script>
Producción:
2 4 6 9 3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por shawavisek35 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA