Dada una array arr[] de n enteros positivos. La tarea es encontrar el tamaño del subconjunto formado por los elementos de la array dada y la diferencia absoluta entre dos elementos cualquiera del conjunto es menor que igual a 1.
Ejemplos:
Input : arr[] = {8, 9, 8, 7, 8, 9, 10, 11}
Output : 5
If we make subset with elements {8, 9, 8, 8, 9}.
Each pair in the subset has an absolute
difference <= 1
Input : arr[] = {4, 5, 2, 4, 4, 4}
Output : 5
Subset is {4, 5, 4, 4, 4}
Observe, dado que queremos que la diferencia absoluta entre dos elementos cualquiera sea menor que igual a 1, entonces puede haber un máximo de dos números distintos. Entonces, el subconjunto que elijamos tendrá la forma {a, a, a, ….., b, b, b} o {a, a, a, a, …..}.
Ahora, para encontrar el tamaño de dicho subconjunto, encontraremos la frecuencia de cada elemento, digamos c 1 , c 2 , c 3 , …., c j , …., c elemento máximo en arr . Entonces nuestra respuesta será el valor máximo de c i + c i+1 .
A continuación se muestra la implementación de este enfoque:
C++
// CPP Program to find the size of
// the subset formed from the elements
// of the given array such that the
// maximum difference is 1
#include <bits/stdc++.h>
using namespace std;
// Return the maximum size of subset with
// absolute difference between any element
// is less than 1.
int maxsizeSubset(int arr[], int n)
{
// Inserting elements and their
// frequencies in a hash table.
unordered_map<int, int> mp;
for (int i = 0; i < n; i++)
mp[arr[i]]++;
// Traverse through map, for every element
// x in map, find if x+1 also exists in map.
// If exists, see if sum of their frequencies
// is more than current result.
int res = 0;
for (auto x : mp)
if (mp.find(x.first + 1) != mp.end())
{
res = max(res, mp[x.first] + mp[x.first+1]);
}
else
{
res=max(res,mp[x.first]);
}
return res;
}
// Driven Program
int main()
{
int arr[] = {1, 2, 2, 3, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxsizeSubset(arr, n) << endl;
return 0;
}
Java
// Java Program to find the size of
// the subset formed from the elements
// of the given array such that the
// maximum difference is 1
import java.util.*;
class GFG
{
// Return the maximum size of subset with
// absolute difference between any element
// is less than 1.
static int maxsizeSubset(int arr[], int n)
{
// Inserting elements and their
// frequencies in a hash table.
Map<Integer, Integer> mp = new HashMap<>();
for (int i = 0; i < n; i++)
{
if (mp.containsKey(arr[i]))
{
mp.put(arr[i], mp.get(arr[i]) + 1);
}
else
{
mp.put(arr[i], 1);
}
}
// Traverse through map, for every element
// x in map, find if x+1 also exists in map.
// If exists, see if sum of their frequencies
// is more than current result.
int res = 0;
for (Map.Entry<Integer, Integer> x : mp.entrySet())
{
if (mp.containsKey(x.getKey() + 1))
{
res = Math.max(res, mp.get(x.getKey()) + mp.get(x.getKey() + 1));
}
else
{
res = Math.max(res, mp.get(x.getKey()));
}
}
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 2, 3, 1, 2};
int n = arr.length;
System.out.println(maxsizeSubset(arr, n));
}
}
/* This code is contributed by PrinciRaj1992 */
Python3
# Python Program to find the size of
# the subset formed from the elements
# of the given array such that the
# maximum difference is 1
# Return the maximum size of subset with
# absolute difference between any element
# is less than 1.
def maxsizeSubset(arr, n):
# Inserting elements and their
# frequencies in a hash table.
mp = {}
for i in range(n):
if (arr[i] in mp):
mp[arr[i]] = mp[arr[i]] + 1
else:
mp[arr[i]] = 1
# Traverse through map, for every element
# x in map, find if x+1 also exists in map.
# If exists, see if sum of their frequencies
# is more than current result.
res = 0
for x,y in mp.items():
if ((x + 1) in mp):
res = max(res, mp[x] + mp[x + 1])
else:
res = max(res, mp[x])
return res
# Driven Program
arr = [1, 2, 2, 3, 1, 2]
n = len(arr)
print(maxsizeSubset(arr, n))
# This code is contributed by Shinjanpatra
C#
// C# Program to find the size of
// the subset formed from the elements
// of the given array such that the
// maximum difference is 1
using System;
using System.Collections.Generic;
class GFG
{
// Return the maximum size of subset with
// absolute difference between any element
// is less than 1.
static int maxsizeSubset(int []arr, int n)
{
// Inserting elements and their
// frequencies in a hash table.
Dictionary<int,
int> mp = new Dictionary<int,
int>();
for (int i = 0 ; i < n; i++)
{
if(mp.ContainsKey(arr[i]))
{
var val = mp[arr[i]];
mp.Remove(arr[i]);
mp.Add(arr[i], val + 1);
}
else
{
mp.Add(arr[i], 1);
}
}
// Traverse through map, for every element
// x in map, find if x+1 also exists in map.
// If exists, see if sum of their frequencies
// is more than current result.
int res = 0;
foreach(KeyValuePair<int, int > x in mp)
{
if (mp.ContainsKey(x.Key + 1))
{
res = Math.Max(res, mp[x.Key] + mp[x.Key + 1]);
}
else
{
res = Math.Max(res, mp[x.Key]);
}
}
return res;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 2, 2, 3, 1, 2};
int n = arr.Length;
Console.WriteLine(maxsizeSubset(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program to find the size of
// the subset formed from the elements
// of the given array such that the
// maximum difference is 1
// Return the maximum size of subset with
// absolute difference between any element
// is less than 1.
function maxsizeSubset(arr, n) {
// Inserting elements and their
// frequencies in a hash table.
let mp = new Map();
for (let i = 0; i < n; i++) {
if (mp.has(arr[i])) {
mp.set(arr[i], mp.get(arr[i]) + 1)
} else {
mp.set(arr[i], 1)
}
}
// Traverse through map, for every element
// x in map, find if x+1 also exists in map.
// If exists, see if sum of their frequencies
// is more than current result.
let res = 0;
for (let x of mp)
if (mp.has(x[0] + 1)) {
res = Math.max(res, mp.get(x[0]) + mp.get(x[0] + 1));
}
else {
res = Math.max(res, mp.get(x[0]));
}
return res;
}
// Driven Program
let arr = [1, 2, 2, 3, 1, 2];
let n = arr.length;
document.write(maxsizeSubset(arr, n) + "<br>");
// This code is contributed by gfgking.
</script>
Producción:
5
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)