Dada una array arr[] de tamaño N , la tarea es encontrar la frecuencia máxima de cualquier elemento de la array incrementando o disminuyendo cada elemento de la array en 1 como máximo una vez.
Ejemplos:
Entrada: arr[] = { 3, 1, 4, 1, 5, 9, 2 }
Salida: 4
Explicación:
Disminuir el valor de arr[0] en 1 modifica arr[] a { 2, 1, 4, 1, 5, 9, 2 }
Incrementar el valor de arr[1] en 1 modifica arr[] a { 2, 2, 4, 1, 5, 9, 2 }
Incrementar el valor de arr[3] en 1 modifica arr[] to { 2, 2, 4, 1, 5, 9, 2 }
Por lo tanto, la frecuencia de un elemento de array (arr[0]) es 4, que es la máxima posible.Entrada: arr[] = { 0, 1, 2, 3, 4, 5, 6 }
Salida: 3
Explicación:
Incrementar el valor de arr[0] en 1 modifica arr[] a { 1, 1, 2, 3, 4, 5, 6 }
Reducir el valor de arr[2] en 1 modifica arr[] a { 1, 1, 1, 3, 4, 5, 6 }
Por lo tanto, la frecuencia de un elemento de array (arr[0]) es 3 que es el máximo posible.
Enfoque: El problema se puede resolver usando la técnica Greedy . La idea es encontrar el elemento más grande y el más pequeño presente en la array y calcular la suma máxima de la frecuencia de tres números consecutivos iterando todos los números en el rango de elementos de la array. Finalmente, imprima la suma máxima obtenida. Siga los pasos a continuación para resolver el problema:
- Encuentre el elemento más grande de la array , digamos, Max .
- Encuentre el elemento más pequeño de la array , por ejemplo, Min .
- Calcule la frecuencia de todos los elementos de la array en el rango [Mín., Máx.] de la array.
- Itere sobre el rango [Min, Max] y calcule la suma máxima de la frecuencia de tres números consecutivos.
- Finalmente, imprima la suma máxima obtenida.
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 maximize the frequency
// of an array element by incrementing or
// decrementing array elements at most once
void max_freq(int arr[], int N)
{
// Stores the largest array element
int Max = *max_element(arr, arr + N);
// Stores the smallest array element
int Min = *min_element(arr, arr + N);
// freq[i]: Stores frequency of
// (i + Min) in the array
int freq[Max - Min + 1] = { 0 };
// Traverse the array
for (int i = 0; i < N; i++) {
// Update frequency
// of arr[i]
freq[arr[i] - Min]++;
}
// Stores maximum frequency of an
// array element by incrementing
// or decrementing array elements
int maxSum = 0;
// Iterate all the numbers over
// the range [Min, Max]
for (int i = 0;
i < (Max - Min - 1); i++) {
// Stores sum of three
// consecutive numbers
int val = freq[i] + freq[i + 1] + freq[i + 2];
// Update maxSum
maxSum = max(maxSum, val);
}
// Print maxSum
cout << maxSum << "\n";
}
// Driver Code
int main()
{
int arr[] = { 3, 1, 4, 1, 5, 9, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
max_freq(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.Arrays;
class GFG{
// Function to maximize the frequency
// of an array element by incrementing or
// decrementing array elements at most once
static void max_freq(int arr[], int N)
{
Arrays.sort(arr);
// Stores the largest array element
int Max = arr[N - 1];
// Stores the smallest array element
int Min = arr[0];
// freq[i]: Stores frequency of
// (i + Min) in the array
int freq[] = new int[Max - Min + 1];
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update frequency
// of arr[i]
freq[arr[i] - Min]++;
}
// Stores maximum frequency of an
// array element by incrementing
// or decrementing array elements
int maxSum = 0;
// Iterate all the numbers over
// the range [Min, Max]
for(int i = 0; i < (Max - Min - 1); i++)
{
// Stores sum of three
// consecutive numbers
int val = freq[i] + freq[i + 1] +
freq[i + 2];
// Update maxSum
maxSum = Math.max(maxSum, val);
}
// Print maxSum
System.out.println(maxSum);
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 3, 1, 4, 1, 5, 9, 2 };
int N = arr.length;
// Function call
max_freq(arr, N);
}
}
// This code is contributed by AnkThon
Python3
# Python3 program to implement # the above approach # Function to maximize the frequency # of an array element by incrementing or # decrementing array elements at most once def max_freq(arr, N): # Stores the largest array element Max = max(arr) # Stores the smallest array element Min = min(arr) # freq[i]: Stores frequency of # (i + Min) in the array freq = [0] * (Max - Min + 1) # Traverse the array for i in range(N): # Update frequency # of arr[i] freq[arr[i] - Min] += 1 # Stores maximum frequency of an # array element by incrementing # or decrementing array elements maxSum = 0 # Iterate all the numbers over # the range [Min, Max] for i in range( Max - Min - 1): # Stores sum of three # consecutive numbers val = freq[i] + freq[i + 1] + freq[i + 2] # Update maxSum maxSum = max(maxSum, val) # Print maxSum print(maxSum) # Driver Code if __name__ == "__main__" : arr = [ 3, 1, 4, 1, 5, 9, 2 ] N = len(arr) # Function call max_freq(arr, N) # This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to maximize the frequency
// of an array element by incrementing or
// decrementing array elements at most once
static void max_freq(int[] arr, int N)
{
Array.Sort(arr);
// Stores the largest array element
int Max = arr[N - 1];
// Stores the smallest array element
int Min = arr[0];
// freq[i]: Stores frequency of
// (i + Min) in the array
int[] freq = new int[Max - Min + 1];
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update frequency
// of arr[i]
freq[arr[i] - Min]++;
}
// Stores maximum frequency of an
// array element by incrementing
// or decrementing array elements
int maxSum = 0;
// Iterate all the numbers over
// the range [Min, Max]
for(int i = 0; i < (Max - Min - 1); i++)
{
// Stores sum of three
// consecutive numbers
int val = freq[i] + freq[i + 1] +
freq[i + 2];
// Update maxSum
maxSum = Math.Max(maxSum, val);
}
// Print maxSum
Console.WriteLine(maxSum);
}
// Driver Code
public static void Main()
{
int[] arr = { 3, 1, 4, 1, 5, 9, 2 };
int N = arr.Length;
// Function call
max_freq(arr, N);
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Javascript program for the above approach
// Function to maximize the frequency
// of an array element by incrementing or
// decrementing array elements at most once
function max_freq(arr, N)
{
arr.sort();
// Stores the largest array element
let Max = arr[N - 1];
// Stores the smallest array element
let Min = arr[0];
// freq[i]: Stores frequency of
// (i + Min) in the array
let freq = [];
for(let i = 0; i < Max - Min + 1 ; i++)
{
freq[i] = 0;
}
// Traverse the array
for(let i = 0; i < N; i++)
{
// Update frequency
// of arr[i]
freq[arr[i] - Min]++;
}
// Stores maximum frequency of an
// array element by incrementing
// or decrementing array elements
let maxSum = 0;
// Iterate all the numbers over
// the range [Min, Max]
for(let i = 0; i < (Max - Min - 1); i++)
{
// Stores sum of three
// consecutive numbers
let val = freq[i] + freq[i + 1] +
freq[i + 2];
// Update maxSum
maxSum = Math.max(maxSum, val);
}
// Print maxSum
document.write(maxSum);
}
// Driver Code
let arr = [ 3, 1, 4, 1, 5, 9, 2 ];
let N = arr.length;
// Function call
max_freq(arr, N);
</script>
4
Complejidad de tiempo: O(N + |Max – Min|), donde Max, Min denotan los elementos de array más grandes y más pequeños respectivamente
Espacio auxiliar: O(|Max – Min|)
Publicación traducida automáticamente
Artículo escrito por priyanshjha99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA