Dado un arreglo arr[] de tamaño N y un entero K , la tarea es encontrar el número máximo de números pares presentes en cualquier subarreglo de tamaño K.
Ejemplos:
Entrada: arr[] = {2, 3, 5, 4, 7, 6}, K = 3
Salida: 2
Explicación:
Los subarreglos de tamaño K(=3) con un recuento máximo de números pares son { arr[3], arr [4], arr[5] }
Por lo tanto, la salida requerida es 2Entrada : arr[] = {4, 3, 2, 6}, K = 2
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subarreglos posibles de tamaño K y contar los números pares en el subarreglo. Finalmente, imprima el conteo máximo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum count of
// even numbers from all the subarrays of
// size K
int maxEvenIntegers(int arr[], int N, int M)
{
// Stores the maximum count of even numbers
// from all the subarrays of size K
int ans = 0;
// Generate all subarrays of size K
for (int i = 0; i <= N - M; i++) {
// Store count of even numbers
// in current subarray of size K
int cnt = 0;
// Traverse the current subarray
for (int j = 0; j < M; j++) {
// If current element
// is an even number
if (arr[i + j] % 2 == 0)
cnt++;
}
// Update the answer
ans = max(ans, cnt);
}
// Return answer
return ans;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 5, 4, 7, 6 };
int K = 3;
// Size of the input array
int N = sizeof(arr) / sizeof(arr[0]);
cout << maxEvenIntegers(arr, N, K) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to find the maximum count of
// even numbers from all the subarrays of
// size K
static int maxEvenIntegers(int arr[], int N, int M)
{
// Stores the maximum count of even numbers
// from all the subarrays of size K
int ans = 0;
// Generate all subarrays of size K
for (int i = 0; i <= N - M; i++)
{
// Store count of even numbers
// in current subarray of size K
int cnt = 0;
// Traverse the current subarray
for (int j = 0; j < M; j++)
{
// If current element
// is an even number
if (arr[i + j] % 2 == 0)
cnt++;
}
// Update the answer
ans = Math.max(ans, cnt);
}
// Return answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 5, 4, 7, 6 };
int K = 3;
// Size of the input array
int N = arr.length;
System.out.print(maxEvenIntegers(arr, N, K) +"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Function to find the maximum count of # even numbers from all the subarrays of # size K def maxEvenIntegers(arr, N, K): # Stores the maximum count of even numbers # from all the subarrays of size K ans = 0 # Generate all subarrays of size K for i in range(N-K+1): # Store count of even numbers # in current subarray of size K cnt = 0 # Traverse the current subarray for j in range(0, K): if arr[i+j] % 2 == 0: cnt += 1 # Update the answer ans = max(cnt, ans) # Return answer return ans # Driver Code if __name__ == '__main__': arr = [2, 3, 5, 4, 7, 6] K = 3 # Size of the input array N = len(arr) print(maxEvenIntegers(arr, N, K)) # This code is contributed by MuskanKalra1
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the maximum count of
// even numbers from all the subarrays of
// size K
static int maxEvenIntegers(int []arr, int N, int M)
{
// Stores the maximum count of even numbers
// from all the subarrays of size K
int ans = 0;
// Generate all subarrays of size K
for (int i = 0; i <= N - M; i++)
{
// Store count of even numbers
// in current subarray of size K
int cnt = 0;
// Traverse the current subarray
for (int j = 0; j < M; j++)
{
// If current element
// is an even number
if (arr[i + j] % 2 == 0)
cnt++;
}
// Update the answer
ans = Math.Max(ans, cnt);
}
// Return answer
return ans;
}
// Driver Code
public static void Main(string[] args)
{
int []arr = { 2, 3, 5, 4, 7, 6 };
int K = 3;
// Size of the input array
int N = arr.Length;
Console.WriteLine(maxEvenIntegers(arr, N, K));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Java script program to implement
// the above approach
// Function to find the maximum count of
// even numbers from all the subarrays of
// size K
function maxEvenIntegers(arr, N, M)
{
// Stores the maximum count of even numbers
// from all the subarrays of size K
let ans = 0;
// Generate all subarrays of size K
for (let i = 0; i <= N - M; i++)
{
// Store count of even numbers
// in current subarray of size K
let cnt = 0;
// Traverse the current subarray
for (let j = 0; j < M; j++)
{
// If current element
// is an even number
if (arr[i + j] % 2 == 0)
cnt++;
}
// Update the answer
ans = Math.max(ans, cnt);
}
// Return answer
return ans;
}
// Driver Code
let arr = [ 2, 3, 5, 4, 7, 6 ];
let K = 3;
// Size of the input array
let N = arr.length;
document.write(maxEvenIntegers(arr, N, K) +"<br>");
//contributed by bobby
</script>
Producción:
2
Complejidad temporal: O(N * K)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la técnica de la ventana deslizante . Siga los pasos a continuación para resolver los problemas:
- Inicialice una variable, digamos cntMaxEven , para almacenar el recuento máximo de números pares en un subarreglo de tamaño K.
- Calcule el recuento de números pares en el subarreglo { arr[0], … arr[K – 1] } y guárdelo en cntMaxEven .
- Atraviese los subarreglos restantes de tamaño K iterando sobre el rango [K, N – 1] . Para cada i- ésima iteración, elimine el primer elemento del subarreglo e inserte el i- ésimo elemento actual del arreglo en el subarreglo actual.
- Cuente los números pares en el subarreglo actual y actualice cntMaxEven al conteo máximo de números pares en el subarreglo actual y cntMaxEven .
- Finalmente, imprima el valor de cntMaxEven .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum count of
// even numbers from all the subarrays of
// size K
int maxEvenIntegers(int arr[], int N, int M)
{
// Stores the count of even numbers
// in a subarray of size K
int curr = 0;
// Calculate the count of even numbers
// in the current subarray
for (int i = 0; i < M; i++) {
// If current element is
// an even number
if (arr[i] % 2 == 0)
curr++;
}
// Stores the maximum count of even numbers
// from all the subarrays of size K
int ans = curr;
// Traverse remaining subarrays of size K
// using sliding window technique
for (int i = M; i < N; i++) {
// If the first element of
// the subarray is even
if (arr[i - M] % 2 == 0) {
// Update curr
curr--;
}
// If i-th element is even increment
// the count
if (arr[i] % 2 == 0)
curr++;
// Update the answer
ans = max(ans, curr);
}
// Return answer
return ans;
}
// Driver Code
int main()
{
int arr[] = { 2, 3, 5, 4, 7, 6 };
int M = 3;
// Size of the input array
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << maxEvenIntegers(arr, N, M) << endl;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to find the maximum count of
// even numbers from all the subarrays of
// size K
static int maxEvenIntegers(int arr[], int N, int M)
{
// Stores the count of even numbers
// in a subarray of size K
int curr = 0;
// Calculate the count of even numbers
// in the current subarray
for (int i = 0; i < M; i++)
{
// If current element is
// an even number
if (arr[i] % 2 == 0)
curr++;
}
// Stores the maximum count of even numbers
// from all the subarrays of size K
int ans = curr;
// Traverse remaining subarrays of size K
// using sliding window technique
for (int i = M; i < N; i++)
{
// If the first element of
// the subarray is even
if (arr[i - M] % 2 == 0)
{
// Update curr
curr--;
}
// If i-th element is even increment
// the count
if (arr[i] % 2 == 0)
curr++;
// Update the answer
ans = Math.max(ans, curr);
}
// Return answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 3, 5, 4, 7, 6 };
int M = 3;
// Size of the input array
int N = arr.length;
// Function call
System.out.print(maxEvenIntegers(arr, N, M) +"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Function to find the maximum count of # even numbers from all the subarrays of # size M def maxEvenIntegers(arr, N, M): # Stores the count of even numbers # in a subarray of size M curr = 0 # Calculate the count of even numbers # in the current subarray for i in range(0, M): # If current element is # an even number if(arr[i] % 2 == 0): curr += 1 # Stores the maximum count of even numbers # from all the subarrays of size M ans = curr # Traverse remaining subarrays of size M # using sliding window technique for i in range(M, N): # If the first element of # the subarray is even if(arr[i - M] % 2 == 0): # update curr curr -= 1 # If i-th element is even increment # the count if(arr[i] % 2 == 0): curr += 1 # update the answer ans = max(curr, ans) # Return answer return ans # Driver Code if __name__ == '__main__': arr = [2, 3, 5, 4, 7, 6] M = 3 # Size of the input array N = len(arr) # Function call print(maxEvenIntegers(arr, N, M)) # This code is contributed by MuskanKalra1
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the maximum count of
// even numbers from all the subarrays of
// size K
static int maxEvenints(int []arr, int N, int M)
{
// Stores the count of even numbers
// in a subarray of size K
int curr = 0;
// Calculate the count of even numbers
// in the current subarray
for (int i = 0; i < M; i++)
{
// If current element is
// an even number
if (arr[i] % 2 == 0)
curr++;
}
// Stores the maximum count of even numbers
// from all the subarrays of size K
int ans = curr;
// Traverse remaining subarrays of size K
// using sliding window technique
for (int i = M; i < N; i++)
{
// If the first element of
// the subarray is even
if (arr[i - M] % 2 == 0)
{
// Update curr
curr--;
}
// If i-th element is even increment
// the count
if (arr[i] % 2 == 0)
curr++;
// Update the answer
ans = Math.Max(ans, curr);
}
// Return answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 3, 5, 4, 7, 6 };
int M = 3;
// Size of the input array
int N = arr.Length;
// Function call
Console.Write(maxEvenints(arr, N, M) +"\n");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the maximum count of
// even numbers from all the subarrays of
// size K
function maxEvenLetegers(arr, N, M)
{
// Stores the count of even numbers
// in a subarray of size K
let curr = 0;
// Calculate the count of even numbers
// in the current subarray
for (let i = 0; i < M; i++)
{
// If current element is
// an even number
if (arr[i] % 2 == 0)
curr++;
}
// Stores the maximum count of even numbers
// from all the subarrays of size K
let ans = curr;
// Traverse remaining subarrays of size K
// using sliding window technique
for (let i = M; i < N; i++)
{
// If the first element of
// the subarray is even
if (arr[i - M] % 2 == 0)
{
// Update curr
curr--;
}
// If i-th element is even increment
// the count
if (arr[i] % 2 == 0)
curr++;
// Update the answer
ans = Math.max(ans, curr);
}
// Return answer
return ans;
}
// Driver Code
let arr = [ 2, 3, 5, 4, 7, 6 ];
let M = 3;
// Size of the input array
let N = arr.length;
// Function call
document.write(maxEvenLetegers(arr, N, M) +"\n");
// This code is contributed by souravghosh0416.
</script>
Producción:
2
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA