Dada una array arr[] que contiene N enteros donde 0 ≤ A[ i ] ≤ N , la tarea es dividir la array en dos partes iguales de modo que el MEX de ambas partes sea el mismo , de lo contrario, imprima -1.
Nota: El MEX (mínimo excluido) de una array es el entero no negativo más pequeño que no existe en la array.
Ejemplos:
Entrada: N = 6, arr[] = {1, 6, 2, 3, 5, 2}
Salida:
0
1 2 5
2 3 6
Explicación: Después de dividir la array dada en {1, 2, 5} y {2 , 3, 6}, MEX de ambas arrays es igual (es decir, e MEX = 0)Entrada: N = 4, arr[] = {0, 0, 1, 2}
Salida: -1
Explicación: No es posible dividir una array en dos arrays diferentes
Intuición: como se mencionó, MEX es el entero no negativo más pequeño que no pertenece a la array. Entonces, cualquier número más pequeño no negativo que no esté presente en la array dada puede convertirse en el MEX para ambas arrays de salida.
Para hacer un número entero X, MEX para ambas arrays, todos los elementos menores que X deben presentarse al menos una vez en ambas arrays de salida.
Por ejemplo:
Array = [1, 4, 2, 4, 2, 1, 1]
Luego divida la array en [1, 1, 2, 4] y [1, 2, 4]
Si cualquier elemento menor que X está presente en la array dada solo una vez, entonces no es posible dividir la array dada en dos arrays de igual MEX.
Ejemplo:
array = [1, 2, 3, 4, 4, 2, 1]
En este ejemplo, 3 solo está presente 1 vez en una array dada, por lo que si intentamos dividirlo en 2 arrays, entonces MEX de ambas arrays no es igual.
[1, 2, 3, 4] : MEX = 5
[1, 2, 4] : MEX = 3
Enfoque: La solución al problema se basa en el concepto de hashmap . Siga los pasos que se mencionan a continuación:
- Cree un mapa hash para verificar si algún elemento único está presente en la array o no.
- Iterar de 0 a N y en cada iteración comprobar
- Si la frecuencia de ese elemento es 1, entonces no es posible dividir la array en dos de modo que su MEX sea igual
- Si la frecuencia de ese elemento es 0, entonces podemos dividir la array.
- Si la frecuencia de ese elemento es mayor que 1, busque el siguiente elemento.
- Ordene la array dada y divida la array de acuerdo con su índice par o impar, de modo que si algún elemento está presente 2 o más de 2 veces en la array, luego de dividir ambas arrays de salida consiste al menos 1 vez que los elementos mantienen igual MEX .
- Imprime ambas arrays.
A continuación se muestra la implementación del código:
C++
// C++ code to implement the above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// Least common missing no.
void MEX_arr(int* A, int N)
{
unordered_map<int, int> mp;
bool status = true;
// Push all array elements
// Into unordered_map
for (int i = 0; i < N; i++) {
mp[A[i]]++;
}
// Check any unique element is present
// In array or any element
// Which is not array;
for (int i = 0; i <= N; i++) {
if (mp[i] == 0) {
cout << i << "\n";
break;
}
if (mp[i] == 1) {
status = false;
break;
}
}
if (status == true) {
// Sort the array
sort(A, A + N);
int A1[N / 2], A2[N / 2];
// Push all elements at even index
// in first array and at odd index
// into another array
for (int i = 0; i < N / 2; i++) {
A1[i] = A[2 * i];
A2[i] = A[2 * i + 1];
}
// Print both the arrays
for (int i = 0; i < N / 2; i++) {
cout << A1[i] << " ";
}
cout << "\n";
for (int i = 0; i < N / 2; i++) {
cout << A2[i] << " ";
}
}
// If not possible to divide
// into two array, print -1
else
cout << -1;
}
// Driver code
int main()
{
int N = 6;
int arr[N] = { 1, 6, 2, 3, 5, 2 };
unordered_map<int, int> mp;
// Function call
MEX_arr(arr, N);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the
// Least common missing no.
public static void MEX_arr(int A[], int N)
{
HashMap<Integer, Integer> mp = new HashMap<>();
boolean status = true;
// Push all array elements
// Into HashMap
for (int i = 0; i < N; i++) {
if (mp.get(A[i]) != null)
mp.put(A[i], mp.get(A[i]) + 1);
else
mp.put(A[i], 1);
}
// Check any unique element is present
// In array or any element
// Which is not array;
for (int i = 0; i <= N; i++) {
if (mp.get(i) == null) {
System.out.println(i);
break;
}
if (mp.get(i) == 1) {
status = false;
break;
}
}
if (status == true) {
// Sort the array
Arrays.sort(A);
int A1[] = new int[N / 2];
int A2[] = new int[N / 2];
// Push all elements at even index
// in first array and at odd index
// into another array
for (int i = 0; i < N / 2; i++) {
A1[i] = A[2 * i];
A2[i] = A[2 * i + 1];
}
// Print both the arrays
for (int i = 0; i < N / 2; i++) {
System.out.print(A1[i] + " ");
}
System.out.println();
for (int i = 0; i < N / 2; i++) {
System.out.print(A2[i] + " ");
}
}
// If not possible to divide
// into two array, print -1
else
System.out.print(-1);
}
public static void main(String[] args)
{
int N = 6;
int arr[] = { 1, 6, 2, 3, 5, 2 };
// Function call
MEX_arr(arr, N);
}
}
// This code is contributed by Rohit Pradhan.
Python3
# python3 code to implement the above approach:
# Function to find the
# Least common missing no.
def MEX_arr(A, N):
mp = {}
status = True
# Push all array elements
# Into unordered_map
for i in range(0, N):
mp[A[i]] = mp[A[i]]+1 if A[i] in mp else 1
# Check any unique element is present
# In array or any element
# Which is not array;
for i in range(0, N+1):
if (not i in mp):
print(i)
break
elif (mp[i] == 1):
status = False
break
if (status == True):
# Sort the array
A.sort()
A1, A2 = [0 for _ in range(N // 2)], [0 for _ in range(N // 2)]
# Push all elements at even index
# in first array and at odd index
# into another array
for i in range(0, N//2):
A1[i] = A[2 * i]
A2[i] = A[2 * i + 1]
# Print both the arrays
for i in range(0, N//2):
print(A1[i], end=" ")
print()
for i in range(0, N // 2):
print(A2[i], end=" ")
# If not possible to divide
# into two array, print -1
else:
print(-1)
# Driver code
if __name__ == "__main__":
N = 6
arr = [1, 6, 2, 3, 5, 2]
# unordered_map<int, int> mp;
# Function call
MEX_arr(arr, N)
# This code is contributed by rakeshsahni
C#
// C# code to implement the above approach:
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the
// Least common missing no.
static void MEX_arr(int []A, int N)
{
Dictionary<int, int> mp =
new Dictionary<int, int>();
bool status = true;
// Push all array elements
// Into unordered_map
for (int i = 0; i < N; i++) {
if(mp.ContainsKey(A[i])) {
mp[A[i]] = mp[A[i]] + 1;
}
else {
mp.Add(A[i], 1);
}
}
// Check any unique element is present
// In array or any element
// Which is not array;
for (int i = 0; i <= N; i++) {
if (!mp.ContainsKey(i)) {
Console.WriteLine(i);
break;
}
if (mp[i] == 1) {
status = false;
break;
}
}
if (status == true) {
// Sort the array
Array.Sort(A);
int []A1 = new int[N / 2];
int []A2 = new int[N / 2];
// Push all elements at even index
// in first array and at odd index
// into another array
for (int i = 0; i < N / 2; i++) {
A1[i] = A[2 * i];
A2[i] = A[2 * i + 1];
}
// Print both the arrays
for (int i = 0; i < N / 2; i++) {
Console.Write(A1[i] + " ");
}
Console.WriteLine();
for (int i = 0; i < N / 2; i++) {
Console.Write(A2[i] + " ");
}
}
// If not possible to divide
// into two array, print -1
else
Console.Write(-1);
}
// Driver code
public static void Main()
{
int N = 6;
int []arr = { 1, 6, 2, 3, 5, 2 };
// Function call
MEX_arr(arr, N);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the
// Least common missing no.
function MEX_arr(A, N) {
let mp = new Map();
var status = true;
// Push all array elements
// Into unordered_map
for (let i = 0; i < N; i++) {
if (!mp.has(A[i])) {
mp.set(A[i], 1);
}
else {
mp.set(A[i], mp.get(A[i]) + 1)
}
}
// Check any unique element is present
// In array or any element
// Which is not array;
for (let i = 0; i <= N; i++) {
if (!mp.has(i)) {
document.write(i + '<br>')
break;
}
else if (mp.get(i) == 1) {
status = false;
break;
}
}
if (status == true) {
// Sort the array
A.sort(function (a, b) { return a - b })
let A1 = new Array(Math.floor(N / 2));
let A2 = new Array(Math.floor(N / 2));
// Push all elements at even index
// in first array and at odd index
// into another array
for (let i = 0; i < Math.floor(N / 2); i++) {
A1[i] = A[2 * i];
A2[i] = A[2 * i + 1];
}
// Print both the arrays
for (let i = 0; i < N / 2; i++) {
document.write(A1[i] + ' ')
}
document.write('<br>')
for (let i = 0; i < N / 2; i++) {
document.write(A2[i] + ' ')
}
}
// If not possible to divide
// into two array, print -1
else
document.write(-1)
}
// Driver code
let N = 6;
let arr = [1, 6, 2, 3, 5, 2];
// Function call
MEX_arr(arr, N);
// This code is contributed by Potta Lokesh
</script>
0 1 2 5 2 3 6
Complejidad temporal: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por khatriharsh281 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA