Dada una array arr[] de N elementos, la tarea es maximizar el recuento de elementos distintos en la array, mediante cualquiera de las operaciones dadas en cada elemento de la array:
- ya sea aumentando el elemento en 1
- o disminuyendo el elemento en 1
- o mantener el elemento como está.
Nota: Ningún elemento puede ser menor o igual a 0.
Ejemplos:
Entrada: arr = [4, 4, 5, 5, 5, 5, 6, 6]
Salida: 5
Explicación: Después de modificar cada elemento del arreglo en cualquiera de las tres formas posibles, arr[] = [3, 4 , 5, 5, 5, 5, 6, 7] . Aquí los elementos distintos son 5.Entrada: arr = [1, 1, 1, 8, 8, 8, 9, 9]
Salida: 6
Explicación: Después de modificar cada elemento del arreglo en cualquiera de las tres formas posibles, arr[] = [1, 1 , 2, 7, 8, 8, 9, 10]. Aquí los elementos distintos son 6.
Enfoque: la idea es ordenar primero la array dada, de modo que los elementos se puedan verificar fácilmente, si es distinto, comparándolos con elementos adyacentes.
- Primero, ordene todos los elementos de la array.
- Inicialice las variables count y prev a 0. (Para almacenar el recuento de elementos distintos y el elemento anterior, respectivamente).
- Después de eso, mantenga un registro del elemento anterior usando la variable anterior .
- Iterar la array ordenada.
- Disminuya el valor del elemento actual en 1 y verifique si el elemento anterior es menor que el valor disminuido. Si es menor, incremente el conteo y asigne el valor actual a anterior .
- Si el valor reducido del elemento actual no es mayor que el elemento anterior, mantenga el elemento actual como está y verifique si el elemento anterior es menor que el elemento actual. Si es menor, incremente el conteo y asigne el valor actual a anterior .
- Si el valor actual no es mayor que el elemento anterior, incremente el valor actual en 1 y verifique si el elemento anterior es menor que el elemento actual incrementado. Si es menor, incremente el conteo y asigne el valor actual a anterior .
- Si el valor incrementado del elemento actual no es menor que el valor anterior, omita ese elemento.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Maximize distinct
// elements by incrementing/decrementing
// an element or keeping it same
#include <bits/stdc++.h>
using namespace std;
// Function that Maximize
// the count of distinct
// element
int max_dist_ele(int arr[],
int n)
{
// sort the array
sort(arr, arr + n);
int ans = 0;
// keeping track of
// previous change
int prev = 0;
for (int i = 0;
i < n; i++) {
// check the
// decremented value
if (prev < (arr[i] - 1)) {
ans++;
prev = arr[i] - 1;
}
// check the current
// value
else if (prev < (arr[i])) {
ans++;
prev = arr[i];
}
// check the
// incremented value
else if (prev < (arr[i] + 1)) {
ans++;
prev = arr[i] + 1;
}
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 1, 1, 8,
8, 8, 9, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << max_dist_ele(arr, n)
<< endl;
return 0;
}
Java
// Java program to Maximize
// the count of distinct element
import java.util.*;
public class GFG {
// Function that Maximize
// the count of distinct element
static int max_dist_ele(
int arr[], int n)
{
// sort the array
Arrays.sort(arr);
int ans = 0;
// keeping track of
// previous change
int prev = 0;
for (int i = 0;
i < n; i++) {
// decrement is possible
if (prev < (arr[i] - 1)) {
ans++;
prev = arr[i] - 1;
}
// remain as it is
else if (prev < (arr[i])) {
ans++;
prev = arr[i];
}
// increment is possible
else if (prev < (arr[i] + 1)) {
ans++;
prev = arr[i] + 1;
}
}
return ans;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 1, 1, 8,
8, 8, 9, 9 };
int n = arr.length;
System.out.println(max_dist_ele(arr, n));
}
}
Python3
# Python3 program to Maximize # the count of distinct element def max_dist_ele(arr, n): # Sort the list arr.sort() ans = 0 # Keeping track of # previous change prev = 0 for i in range(n): # Decrement is possible if prev < (arr[i] - 1): ans += 1; prev = arr[i] - 1 # Remain as it is elif prev < (arr[i]): ans += 1 prev = arr[i] # Increment is possible elif prev < (arr[i] + 1): ans += 1 prev = arr[i] + 1 return ans # Driver Code arr = [ 1, 1, 1, 8, 8, 8, 9, 9 ] n = len(arr) print(max_dist_ele(arr, n)) # This code is contributed by rutvik_56
C#
// C# program to maximize the
// count of distinct element
using System;
class GFG{
// Function that maximize the
// count of distinct element
static int max_dist_ele(int []arr, int n)
{
// Sort the array
Array.Sort(arr);
int ans = 0;
// Keeping track of
// previous change
int prev = 0;
for(int i = 0; i < n; i++)
{
// Decrement is possible
if (prev < (arr[i] - 1))
{
ans++;
prev = arr[i] - 1;
}
// Remain as it is
else if (prev < (arr[i]))
{
ans++;
prev = arr[i];
}
// Increment is possible
else if (prev < (arr[i] + 1))
{
ans++;
prev = arr[i] + 1;
}
}
return ans;
}
// Driver Code
public static void Main(String []args)
{
int []arr = { 1, 1, 1, 8,
8, 8, 9, 9 };
int n = arr.Length;
Console.WriteLine(max_dist_ele(arr, n));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to Maximize distinct
// elements by incrementing/decrementing
// an element or keeping it same
// Function that Maximize
// the count of distinct
// element
function max_dist_ele( arr, n)
{
// sort the array
arr.sort();
var ans = 0;
// keeping track of
// previous change
var prev = 0;
for (let i = 0;
i < n; i++) {
// check the
// decremented value
if (prev < (arr[i] - 1)) {
ans++;
prev = arr[i] - 1;
}
// check the current
// value
else if (prev < (arr[i])) {
ans++;
prev = arr[i];
}
// check the
// incremented value
else if (prev < (arr[i] + 1)) {
ans++;
prev = arr[i] + 1;
}
}
return ans;
}
// Driver Code
var arr = new Array( 1, 1, 1, 8,
8, 8, 9, 9 );
var n = arr.length;
document.write(max_dist_ele(arr, n));
// This code is contributed by ukasp.
</script>
Producción:
6
Complejidad de tiempo: O(N*logN)