Dada una array arr[ ] que consta de N enteros, la tarea es determinar el número máximo de Números perfectos en cualquier subarreglo de tamaño K .
Ejemplos:
Entrada: arr[ ] = {28, 2, 3, 6, 496, 99, 8128, 24}, K = 4
Salida: 3
Explicación: El subarreglo {6, 496, 99, 8128} tiene 3 números perfectos que es máximo.Entrada: arr[ ]= {1, 2, 3, 6}, K=2
Salida: 1
Enfoque ingenuo: el enfoque consiste en generar todos los subarreglos posibles de tamaño K y, para cada subarreglo, contar la cantidad de elementos que son un número perfecto . Imprime el conteo máximo obtenido para cualquier subarreglo.
Tiempo Complejidad :O(N*K)
Espacio Auxiliar: O(1)
Enfoque eficiente:
para optimizar el enfoque anterior, convierta la array dada arr[ ] en una array binaria donde el i -ésimo elemento es 1 si es un número perfecto . De lo contrario, el i- ésimo elemento es 0 . Por lo tanto, el problema se reduce a encontrar el subarreglo de suma máxima de tamaño K en el arreglo binario usando la técnica de Ventana Deslizante . Siga los pasos a continuación para resolver el problema:
- Recorra la array y para cada elemento de la array arr[] , verifique si es un número perfecto o no.
- Si arr[i] es un número perfecto , entonces convierta arr[i] igual a 1. De lo contrario, convierta arr[i] igual a 0 .
- Para comprobar si un número es un número perfecto o no :
- Inicialice una suma variable para almacenar la suma de los divisores .
- Recorra cada número en el rango [1, arr[i] – 1] y verifique si es un divisor de arr[i] o no. Suma todos los divisores.
- Si la suma de todos los divisores es igual a arr[i] , entonces el número es un número perfecto . De lo contrario, el número no es un número perfecto .
- Calcule la suma del primer subarreglo de tamaño K en el arreglo modificado.
- Utilizando la técnica de la ventana deslizante , encuentre la suma máxima de un subarreglo de todos los subarreglos posibles de tamaño K.
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 a number
// is Perfect Number or not
int isPerfect(int N)
{
// Stores sum of divisors
int sum = 1;
// Find all divisors and add them
for (int i = 2; i < sqrt(N); i++)
{
if (N % i == 0) {
if (i == N / i)
{
sum += i;
}
else
{
sum += i + N / i;
}
}
}
// If sum of divisors
// is equal to N
if (sum == N && N != 1)
return 1;
return 0;
}
// Function to return maximum
// sum of a subarray of size K
int maxSum(int arr[], int N, int K)
{
// If k is greater than N
if (N < K)
{
cout << "Invalid";
return -1;
}
// Compute sum of first window of size K
int res = 0;
for (int i = 0; i < K; i++)
{
res += arr[i];
}
// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window
int curr_sum = res;
for (int i = K; i < N; i++)
{
curr_sum += arr[i] - arr[i - K];
res = max(res, curr_sum);
}
// return the answer
return res;
}
// Function to find all the
// perfect numbers in the array
int max_PerfectNumbers(int arr[], int N, int K)
{
// The given array is converted into binary array
for (int i = 0; i < N; i++)
{
arr[i] = isPerfect(arr[i]) ? 1 : 0;
}
return maxSum(arr, N, K);
}
// Driver Code
int main()
{
int arr[] = { 28, 2, 3, 6, 496, 99, 8128, 24 };
int K = 4;
int N = sizeof(arr) / sizeof(arr[0]);
cout << max_PerfectNumbers(arr, N, K);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
// Function to check a number
// is Perfect Number or not
static int isPerfect(int N)
{
// Stores sum of divisors
int sum = 1;
// Find all divisors and
// add them
for (int i = 2;
i < Math.sqrt(N); i++)
{
if (N % i == 0)
{
if (i == N / i)
{
sum += i;
}
else
{
sum += i + N / i;
}
}
}
// If sum of divisors
// is equal to N
if (sum == N && N != 1)
return 1;
return 0;
}
// Function to return maximum
// sum of a subarray of size K
static int maxSum(int arr[],
int N, int K)
{
// If k is greater than N
if (N < K)
{
System.out.print("Invalid");
return -1;
}
// Compute sum of first
// window of size K
int res = 0;
for (int i = 0; i < K; i++)
{
res += arr[i];
}
// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window
int curr_sum = res;
for (int i = K; i < N; i++)
{
curr_sum += arr[i] - arr[i - K];
res = Math.max(res, curr_sum);
}
// return the answer
return res;
}
// Function to find all the
// perfect numbers in the array
static int max_PerfectNumbers(int arr[],
int N, int K)
{
// The given array is converted
// into binary array
for (int i = 0; i < N; i++)
{
arr[i] = isPerfect(arr[i]) ==
1 ? 1 : 0;
}
return maxSum(arr, N, K);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {28, 2, 3, 6, 496,
99, 8128, 24};
int K = 4;
int N = arr.length;
System.out.print(max_PerfectNumbers(arr,
N, K));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach
# Function to check a number
# is Perfect Number or not
def isPerfect(N):
# Stores sum of divisors
sum = 1
# Find all divisors and add them
for i in range(2, N):
if i * i > N:
break
if (N % i == 0):
if (i == N // i):
sum += i
else:
sum += i + N // i
# If sum of divisors
# is equal to N
if (sum == N and N != 1):
return 1
return 0
# Function to return maximum
# sum of a subarray of size K
def maxSum(arr, N, K):
# If k is greater than N
if (N < K):
print("Invalid")
return -1
# Compute sum of first
# window of size K
res = 0
for i in range(K):
res += arr[i]
# Compute sums of remaining windows by
# removing first element of previous
# window and adding last element of
# current window
curr_sum = res
for i in range(K, N):
curr_sum += arr[i] - arr[i - K]
res = max(res, curr_sum)
# print(res)
# Return the answer
return res
# Function to find all the
# perfect numbers in the array
def max_PerfectNumbers(arr, N, K):
# The given array is converted
# into binary array
for i in range(N):
if isPerfect(arr[i]):
arr[i] = 1
else:
arr[i] = 0
return maxSum(arr, N, K)
# Driver Code
if __name__ == '__main__':
arr = [ 28, 2, 3, 6,
496, 99, 8128, 24 ]
K = 4
N = len(arr)
print(max_PerfectNumbers(arr, N, K))
# This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
class GFG{
// Function to check a number
// is Perfect Number or not
static int isPerfect(int N)
{
// Stores sum of divisors
int sum = 1;
// Find all divisors and
// add them
for (int i = 2;
i < Math.Sqrt(N); i++)
{
if (N % i == 0)
{
if (i == N / i)
{
sum += i;
}
else
{
sum += i + N / i;
}
}
}
// If sum of divisors
// is equal to N
if (sum == N && N != 1)
return 1;
return 0;
}
// Function to return maximum
// sum of a subarray of size K
static int maxSum(int []arr,
int N, int K)
{
// If k is greater than N
if (N < K)
{
Console.Write("Invalid");
return -1;
}
// Compute sum of first
// window of size K
int res = 0;
for (int i = 0; i < K; i++)
{
res += arr[i];
}
// Compute sums of remaining
// windows by removing first
// element of previous window
// and adding last element of
// current window
int curr_sum = res;
for (int i = K; i < N; i++)
{
curr_sum += arr[i] - arr[i - K];
res = Math.Max(res, curr_sum);
}
// return the answer
return res;
}
// Function to find all the
// perfect numbers in the array
static int max_PerfectNumbers(int []arr,
int N, int K)
{
// The given array is converted
// into binary array
for (int i = 0; i < N; i++)
{
arr[i] = isPerfect(arr[i]) ==
1 ? 1 : 0;
}
return maxSum(arr, N, K);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {28, 2, 3, 6, 496,
99, 8128, 24};
int K = 4;
int N = arr.Length;
Console.Write(max_PerfectNumbers(arr,
N, K));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// Function to check a number
// is Perfect Number or not
function isPerfect(N)
{
// Stores sum of divisors
let sum = 1;
// Find all divisors and
// add them
for(let i = 2;
i < Math.sqrt(N); i++)
{
if (N % i == 0)
{
if (i == N / i)
{
sum += i;
}
else
{
sum += i + N / i;
}
}
}
// If sum of divisors
// is equal to N
if (sum == N && N != 1)
return 1;
return 0;
}
// Function to return maximum
// sum of a subarray of size K
function maxSum(arr, N, K)
{
// If k is greater than N
if (N < K)
{
document.write("Invalid");
return -1;
}
// Compute sum of first
// window of size K
let res = 0;
for(let i = 0; i < K; i++)
{
res += arr[i];
}
// Compute sums of remaining windows by
// removing first element of previous
// window and adding last element of
// current window
let curr_sum = res;
for(let i = K; i < N; i++)
{
curr_sum += arr[i] - arr[i - K];
res = Math.max(res, curr_sum);
}
// Return the answer
return res;
}
// Function to find all the
// perfect numbers in the array
function max_PerfectNumbers(arr, N, K)
{
// The given array is converted
// into binary array
for(let i = 0; i < N; i++)
{
arr[i] = isPerfect(arr[i]) ==
1 ? 1 : 0;
}
return maxSum(arr, N, K);
}
// Driver Code
let arr = [ 28, 2, 3, 6, 496,
99, 8128, 24 ];
let K = 4;
let N = arr.length;
document.write(max_PerfectNumbers(arr, N, K));
// This code is contributed by target_2
</script>
Producción:
3
Complejidad de tiempo: O( N * sqrt(N) )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ArifShaikh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA