Dada una array arr que contiene N enteros, la tarea es encontrar el número más grande en la array cuya frecuencia es igual a su valor. Si no existe tal número, imprima -1.
Ejemplos:
Entrada: arr = [3, 2, 5, 2, 4, 5]
Salida: 2
Explicación:
En esta array dada, la frecuencia de 2 es 2, mientras que la frecuencia de los números restantes no coincide consigo misma. Entonces la respuesta es 2.
Entrada: arr = [3, 3, 3, 4, 4, 4, 4]
Salida: 4
Explicación:
En esta array dada, la frecuencia de 3 es 3 y 4 es 4 pero el número más grande es 4. Entonces la respuesta es 4.
Entrada: arr = [1, 1, 1, 2, 3, 3]
Salida: -1
Explicación:
No existe tal número en la array dada cuya frecuencia sea igual a sí misma. Por lo tanto, la salida es -1.
Enfoque sencillo:
- Cree una nueva array para mantener el recuento de las ocurrencias en la array dada.
- Atraviese la nueva array en orden inverso.
- Devuelve el primer número cuya cuenta es igual a sí mismo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ solution to the above problem
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest number
// whose frequency is equal to itself.
int findLargestNumber(vector<int>& arr)
{
// Find the maximum element in the array
int k = *max_element(arr.begin(),
arr.end());
int m[k] = {};
for (auto n : arr)
++m[n];
for (auto n = arr.size(); n > 0; --n) {
if (n == m[n])
return n;
}
return -1;
}
// Driver code
int main()
{
vector<int> arr = { 3, 2, 5, 2, 4, 5 };
cout << findLargestNumber(arr) << endl;
return 0;
}
Java
// Java solution to the above problem
import java.util.*;
class GFG{
// Function to find the largest number
// whose frequency is equal to itself.
static int findLargestNumber(int[] arr)
{
// Find the maximum element in the array
int k = Arrays.stream(arr).max().getAsInt();
int []m = new int[k + 1];
for(int n : arr)
++m[n];
for(int n = arr.length - 1; n > 0; --n)
{
if (n == m[n])
return n;
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 3, 2, 5, 2, 4, 5 };
System.out.print(findLargestNumber(arr) + "\n");
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 solution to the above problem # Function to find the largest number # whose frequency is equal to itself. def findLargestNumber(arr): # Find the maximum element in the array k = max(arr); m = [0] * (k + 1); for n in arr: m[n] += 1; for n in range(len(arr) - 1, 0, -1): if (n == m[n]): return n; return -1; # Driver code if __name__ == '__main__': arr = [ 3, 2, 5, 2, 4, 5 ]; print(findLargestNumber(arr)); # This code is contributed by amal kumar choubey
C#
// C# solution to the above problem
using System;
using System.Linq;
class GFG{
// Function to find the largest number
// whose frequency is equal to itself.
static int findLargestNumber(int[] arr)
{
// Find the maximum element in the array
int k = arr.Max();
int []m = new int[k + 1];
foreach(int n in arr)
++m[n];
for(int n = arr.Length - 1; n > 0; --n)
{
if (n == m[n])
return n;
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 3, 2, 5, 2, 4, 5 };
Console.Write(findLargestNumber(arr) + "\n");
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// Javascript solution to the above problem
// Function to find the largest number
// whose frequency is equal to itself.
function findLargestNumber(arr)
{
// Find the maximum element in the array
var k = arr.reduce((a,b)=> Math.max(a,b));
var m = Array(k).fill(0);
arr.forEach(n => {
++m[n];
});
for (var n = arr.length; n > 0; --n) {
if (n == m[n])
return n;
}
return -1;
}
// Driver code
var arr = [3, 2, 5, 2, 4, 5];
document.write( findLargestNumber(arr));
</script>
Producción:
2
Complejidad de tiempo: O(N)
Complejidad de espacio auxiliar: O(N)
Otro enfoque:
Nota: este enfoque es válido solo cuando los números en la array dada son menores que 65536, es decir, 2 16 .
- Aquí, use la array de entrada para almacenar el conteo.
- Dado que los valores son limitados, simplemente use la primera mitad (los primeros 16 bits) del entero para llevar la cuenta sumando 65536.
- Utilice el operador de desplazamiento a la derecha (desplazamiento a la derecha de 16 bits) mientras recorre la array en orden inverso y devuelva el primer número cuyo recuento sea igual a sí mismo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above problem
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest number
// whose frequency is equal to itself.
int findLargestNumber(vector<int>& arr)
{
for (auto n : arr) {
n &= 0xFFFF;
if (n <= arr.size()) {
// Adding 65536 to keep the
// count of the current number
arr[n - 1] += 0x10000;
}
}
for (auto i = arr.size(); i > 0; --i) {
// right shifting by 16 bits
// to find the count of the
// number i
if ((arr[i - 1] >> 16) == i)
return i;
}
return -1;
}
// Driver code
int main()
{
vector<int> arr
= { 3, 2, 5, 5, 2, 4, 5 };
cout << findLargestNumber(arr)
<< endl;
return 0;
}
Java
// Java code for the above problem
class GFG{
// Function to find the largest number
// whose frequency is equal to itself.
static int findLargestNumber(int[] arr, int n)
{
for(int i = 0; i < n; i++)
{
arr[i] &= 0xFFFF;
if (arr[i] <= n)
{
// Adding 65536 to keep the
// count of the current number
arr[i] += 0x10000;
}
}
for(int i = n - 1; i > 0; --i)
{
// Right shifting by 16 bits
// to find the count of the
// number i
if ((arr[i] >> 16) == i)
return i + 1;
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int []arr = { 3, 2, 5, 5, 2, 4, 5 };
int n = arr.length;
System.out.print(findLargestNumber(arr, n) + "\n");
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 code for the above problem # Function to find the largest number # whose frequency is equal to itself. def findLargestNumber(arr, n): for i in range(n): arr[i] &= 0xFFFF; if (arr[i] <= n): # Adding 65536 to keep the # count of the current number arr[i] += 0x10000; for i in range(n - 1, 0, -1): # Right shifting by 16 bits # to find the count of the # number i if ((arr[i] >> 16) == i): return i + 1; return -1; # Driver code if __name__ == '__main__': arr = [ 3, 2, 5, 5, 2, 4, 5 ]; n = len(arr); print(findLargestNumber(arr, n)); # This code is contributed by Rohit_ranjan
C#
// C# code for the above problem
using System;
class GFG{
// Function to find the largest number
// whose frequency is equal to itself.
static int findLargestNumber(int[] arr, int n)
{
for(int i = 0; i < n; i++)
{
arr[i] &= 0xFFFF;
if (arr[i] <= n)
{
// Adding 65536 to keep the
// count of the current number
arr[i] += 0x10000;
}
}
for(int i = n - 1; i > 0; --i)
{
// Right shifting by 16 bits
// to find the count of the
// number i
if ((arr[i] >> 16) == i)
return i + 1;
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 3, 2, 5, 5, 2, 4, 5 };
int n = arr.Length;
Console.Write(findLargestNumber(arr, n) + "\n");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript code for the above problem
// Function to find the largest number
// whose frequency is equal to itself.
function findLargestNumber(arr)
{
arr.forEach(n => {
n &= 0xFFFF;
if (n <= arr.length) {
// Adding 65536 to keep the
// count of the current number
arr[n - 1] += 0x10000;
}
});
for(var i = arr.length; i > 0; --i) {
// right shifting by 16 bits
// to find the count of the
// number i
if ((arr[i - 1] >> 16) == i)
return i;
}
return -1;
}
// Driver code
var arr
= [3, 2, 5, 5, 2, 4, 5];
document.write( findLargestNumber(arr))
// This code is contributed by rrrtnx.
</script>
Producción:
2
Complejidad de Tiempo: O(N)
Complejidad de Espacio Auxiliar: O(1)