Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7}
Salida: 4
Explicación: La distancia entre arr[1] = 2 y arr[5] = 6 es 4, que es la distancia máxima entre dos enteros pares presentes en el arreglo dado.Entrada: arr[] = {3, 5, 6, 9, 11}
Salida: 0
Explicación: La array dada contiene menos de 2 enteros pares. Por lo tanto, la distancia máxima es 0.
Enfoque ingenuo: el problema dado se puede resolver comprobando la distancia entre todos los pares de enteros pares que se encuentran en la array y manteniendo el máximo en ellos, que será la respuesta requerida.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: este problema se puede resolver utilizando el enfoque de dos punteros .
- Manejar el caso con menos de 2 enteros pares por separado.
- El índice de distancia máxima de los enteros pares será el índice de la primera y la última ocurrencia de los enteros pares.
- Esto se puede hacer simplemente recorriendo la array usando dos punteros, uno desde el inicio y otro desde el final.
- Tan pronto como se alcance un entero par desde ambos punteros, devuelva la distancia entre ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the maximum
// distance between any two occurrence
// of even integers in the given array
int maximizeDistance(int arr[], int n)
{
// Stores the index of
// 1st even integer
int i = 0;
// Traverse array arr[]
while (i < n) {
if (arr[i] % 2 == 0) {
break;
}
i++;
}
// Stores the index of
// last even integer
int j = n - 1;
// Traverse array arr[]
// in reverse direction
while (j >= 0) {
if (arr[j] % 2 == 0) {
break;
}
j--;
}
// Case where arr[] has less
// that two even integers
if (i >= j) {
return 0;
}
// Return Answer
return j - i;
}
// Driver Code
int main()
{
int arr[] = { 3, 4, 5, 6, 7, 8 };
int N = sizeof(arr) / sizeof(int);
cout << maximizeDistance(arr, N);
return 0;
}
Java
// Java program to of the above approach
import java.util.*;
public class GFG {
// Function to calculate the maximum
// distance between any two occurrence
// of even integers in the given array
static int maximizeDistance(int arr[], int n)
{
// Stores the index of
// 1st even integer
int i = 0;
// Traverse array arr[]
while (i < n) {
if (arr[i] % 2 == 0) {
break;
}
i++;
}
// Stores the index of
// last even integer
int j = n - 1;
// Traverse array arr[]
// in reverse direction
while (j >= 0) {
if (arr[j] % 2 == 0) {
break;
}
j--;
}
// Case where arr[] has less
// that two even integers
if (i >= j) {
return 0;
}
// Return Answer
return j - i;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 3, 4, 5, 6, 7, 8 };
int N = arr.length;
System.out.print(maximizeDistance(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# python3 program to of the above approach # Function to calculate the maximum # distance between any two occurrence # of even integers in the given array def maximizeDistance(arr, n): # Stores the index of # 1st even integer i = 0 # Traverse array arr[] while (i < n): if (arr[i] % 2 == 0): break i += 1 # Stores the index of # last even integer j = n - 1 # Traverse array arr[] # in reverse direction while (j >= 0): if (arr[j] % 2 == 0): break j -= 1 # Case where arr[] has less # that two even integers if (i >= j): return 0 # Return Answer return j - i # Driver Code if __name__ == "__main__": arr = [3, 4, 5, 6, 7, 8] N = len(arr) print(maximizeDistance(arr, N)) # This code is contributed by rakeshsahni
C#
// C# program to of the above approach
using System;
class GFG {
// Function to calculate the maximum
// distance between any two occurrence
// of even integers in the given array
static int maximizeDistance(int[] arr, int n)
{
// Stores the index of
// 1st even integer
int i = 0;
// Traverse array arr[]
while (i < n) {
if (arr[i] % 2 == 0) {
break;
}
i++;
}
// Stores the index of
// last even integer
int j = n - 1;
// Traverse array arr[]
// in reverse direction
while (j >= 0) {
if (arr[j] % 2 == 0) {
break;
}
j--;
}
// Case where arr[] has less
// that two even integers
if (i >= j) {
return 0;
}
// Return Answer
return j - i;
}
// Driver Code
public static void Main()
{
int[] arr = { 3, 4, 5, 6, 7, 8 };
int N = arr.Length;
Console.Write(maximizeDistance(arr, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to calculate the maximum
// distance between any two occurrence
// of even integers in the given array
function maximizeDistance(arr, n)
{
// Stores the index of
// 1st even integer
let i = 0;
// Traverse array arr[]
while (i < n) {
if (arr[i] % 2 == 0) {
break;
}
i++;
}
// Stores the index of
// last even integer
let j = n - 1;
// Traverse array arr[]
// in reverse direction
while (j >= 0) {
if (arr[j] % 2 == 0) {
break;
}
j--;
}
// Case where arr[] has less
// that two even integers
if (i >= j) {
return 0;
}
// Return Answer
return j - i;
}
// Driver Code
let arr = [3, 4, 5, 6, 7, 8];
let N = arr.length;
document.write(maximizeDistance(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshverma28 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA