Dada una array arr[] de longitud N , la tarea es verificar si se puede formar fusionando dos permutaciones de la misma o diferente longitud. Escriba SÍ si tal fusión es posible. De lo contrario, imprima NO .
Las permutaciones de longitud 3 son {1, 2, 3}, {2, 3, 1}, {1, 3, 2}, {3, 1, 2}, {3, 2, 1}, {2, 1, 3}.
Ejemplos:
Entrada: arr = [1, 3, 2, 4, 3, 1, 2]
Salida: SÍ
Explicación:
La array dada se puede formar fusionando una permutación de longitud 4 [1, 3, 2, 4] y una permutación de longitud 3 [3, 1, 2]Entrada: arr = [1, 2, 3, 2, 3, 2, 1]
Salida: NO
Enfoque:
Podemos observar que el mínimo excluyente (MEX) de una permutación de longitud N es N+1 .
Entonces, si la longitud de la primera permutación es l , entonces MEX del prefijo arr [0 …… l-1] es l+1 y MEX del sufijo a[l …… n] será N – l + 1 .
Entonces, podemos calcular MEX de prefijos y sufijos y si se cumple la condición anterior, la respuesta será «SÍ» . De lo contrario, la respuesta será “NO” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the
// above approach
#include<bits/stdc++.h>
using namespace std;
void if_merged_permutations(int a[],
int n)
{
int pre_mex[n];
// Calculate the mex of the
// array a[0...i]
int freq[n + 1];
memset(freq, 0, sizeof(freq));
for(int i = 0; i < n; i++)
{
pre_mex[i] = 1;
}
// Mex of empty
// array is 1
int mex = 1;
// Calculating the frequency
// of array elements
for(int i = 0; i < n; i++)
{
freq[a[i]]++;
if(freq[a[i]] > 1)
{
// In a permutation
// each element is
// present one time,
// So there is no chance
// of getting permutations
// for the prefix of
// length greater than i
break;
}
// The current element
// is the mex
if(a[i] == mex)
{
// While mex is present
// in the array
while(freq[mex] != 0)
{
mex++;
}
}
pre_mex[i] = mex;
}
int suf_mex[n];
for(int i = 0; i < n; i++)
{
suf_mex[i] = 1;
}
// Calculate the mex of the
// array a[i..n]
memset(freq, 0, sizeof(freq));
// Mex of empty
// array is 1
mex = 1;
// Calculating the frequency
// of array elements
for(int i = n - 1; i > -1; i--)
{
freq[a[i]]++;
if(freq[a[i]] > 1)
{
// In a permutation each
// element is present
// one time, So there is
// no chance of getting
// permutations for the
// suffix of length lesser
// than i
continue;
}
// The current element is
// the mex
if(a[i] == mex)
{
// While mex is present
// in the array
while(freq[mex] != 0)
{
mex++;
}
}
suf_mex[i] = mex;
}
// Now check if there is atleast
// one index i such that mex of
// the prefix a[0..i]= i +
// 2(0 based indexing) and mex
// of the suffix a[i + 1..n]= n-i
for(int i = 0; i < n - 1; i++)
{
if(pre_mex[i] == i + 2 &&
suf_mex[i + 1] == n - i)
{
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
// Driver code
int main()
{
int a[] = {1, 3, 2,
4, 3, 1, 2};
int n = sizeof(a)/ sizeof(a[0]);
if_merged_permutations(a, n);
}
//This code is contributed by avanitrachhadiya2155
Java
// Java program for above approach
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG{
static void if_merged_permutations(int a[],
int n)
{
int[] pre_mex = new int[n];
// Calculate the mex of the
// array a[0...i]
int[] freq = new int[n + 1];
for(int i = 0; i < n; i++)
{
pre_mex[i] = 1;
}
// Mex of empty
// array is 1
int mex = 1;
// Calculating the frequency
// of array elements
for(int i = 0; i < n; i++)
{
freq[a[i]]++;
if (freq[a[i]] > 1)
{
// In a permutation
// each element is
// present one time,
// So there is no chance
// of getting permutations
// for the prefix of
// length greater than i
break;
}
// The current element
// is the mex
if (a[i] == mex)
{
// While mex is present
// in the array
while (freq[mex] != 0)
{
mex++;
}
}
pre_mex[i] = mex;
}
int[] suf_mex = new int[n];
for(int i = 0; i < n; i++)
{
suf_mex[i] = 1;
}
// Calculate the mex of the
// array a[i..n]
Arrays.fill(freq, 0);
// Mex of empty
// array is 1
mex = 1;
// Calculating the frequency
// of array elements
for(int i = n - 1; i > -1; i--)
{
freq[a[i]]++;
if (freq[a[i]] > 1)
{
// In a permutation each
// element is present
// one time, So there is
// no chance of getting
// permutations for the
// suffix of length lesser
// than i
continue;
}
// The current element is
// the mex
if (a[i] == mex)
{
// While mex is present
// in the array
while (freq[mex] != 0)
{
mex++;
}
}
suf_mex[i] = mex;
}
// Now check if there is atleast
// one index i such that mex of
// the prefix a[0..i]= i +
// 2(0 based indexing) and mex
// of the suffix a[i + 1..n]= n-i
for(int i = 0; i < n - 1; i++)
{
if (pre_mex[i] == i + 2 &&
suf_mex[i + 1] == n - i)
{
System.out.println("YES");
return;
}
}
System.out.println("NO");
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 3, 2, 4, 3, 1, 2 };
int n = a.length;
if_merged_permutations(a, n);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for above approach
def if_merged_permutations(a, n):
pre_mex =[1 for i in range(n)]
# Calculate the mex of the
# array a[0...i]
freq =[0 for i in range(n + 1)]
# Mex of empty array is 1
mex = 1
# Calculating the frequency
# of array elements
for i in range(n):
freq[a[i]]+= 1
if freq[a[i]]>1:
# In a permutation
# each element is
# present one time,
# So there is no chance
# of getting permutations
# for the prefix of
# length greater than i
break
# The current element
# is the mex
if a[i]== mex:
# While mex is present
# in the array
while freq[mex]!= 0 :
mex+= 1
pre_mex[i]= mex
suf_mex =[1 for i in range(n)]
# Calculate the mex of the
# array a[i..n]
freq =[0 for i in range(n + 1)]
# Mex of empty array is 1
mex = 1
# Calculating the frequency
# of array elements
for i in range(n-1, -1, -1):
freq[a[i]]+= 1
if freq[a[i]]>1:
# In a permutation each
# element is present
# one time, So there is
# no chance of getting
# permutations for the
# suffix of length lesser
# than i
break
# The current element is
# the mex
if a[i]== mex:
# While mex is present
# in the array
while freq[mex]!= 0 :
mex+= 1
suf_mex[i]= mex
# Now check if there is atleast
# one index i such that mex of
# the prefix a[0..i]= i +
# 2(0 based indexing) and mex
# of the suffix a[i + 1..n]= n-i
for i in range(n-1):
if pre_mex[i]== i + 2 and suf_mex[i + 1]== n-i:
print("YES")
return
print("NO")
a =[1, 3, 2, 4, 3, 1, 2]
n = len(a)
if_merged_permutations(a, n)
C#
// C# program for above approach
using System;
class GFG{
static void if_merged_permutations(int[] a,
int n)
{
int[] pre_mex = new int[n];
// Calculate the mex of the
// array a[0...i]
int[] freq = new int[n + 1];
for(int i = 0; i < n; i++)
{
pre_mex[i] = 1;
}
// Mex of empty
// array is 1
int mex = 1;
// Calculating the frequency
// of array elements
for(int i = 0; i < n; i++)
{
freq[a[i]]++;
if (freq[a[i]] > 1)
{
// In a permutation
// each element is
// present one time,
// So there is no chance
// of getting permutations
// for the prefix of
// length greater than i
break;
}
// The current element
// is the mex
if (a[i] == mex)
{
// While mex is present
// in the array
while (freq[mex] != 0)
{
mex++;
}
}
pre_mex[i] = mex;
}
int[] suf_mex = new int[n];
for(int i = 0; i < n; i++)
{
suf_mex[i] = 1;
}
// Calculate the mex of the
// array a[i..n]
Array.Fill(freq, 0);
// Mex of empty
// array is 1
mex = 1;
// Calculating the frequency
// of array elements
for(int i = n - 1; i > -1; i--)
{
freq[a[i]]++;
if (freq[a[i]] > 1)
{
// In a permutation each
// element is present
// one time, So there is
// no chance of getting
// permutations for the
// suffix of length lesser
// than i
continue;
}
// The current element is
// the mex
if (a[i] == mex)
{
// While mex is present
// in the array
while (freq[mex] != 0)
{
mex++;
}
}
suf_mex[i] = mex;
}
// Now check if there is atleast
// one index i such that mex of
// the prefix a[0..i]= i +
// 2(0 based indexing) and mex
// of the suffix a[i + 1..n]= n-i
for(int i = 0; i < n - 1; i++)
{
if (pre_mex[i] == i + 2 &&
suf_mex[i + 1] == n - i)
{
Console.WriteLine("YES");
return;
}
}
Console.WriteLine("NO");
}
// Driver Code
static void Main()
{
int[] a = { 1, 3, 2, 4, 3, 1, 2 };
int n = a.Length;
if_merged_permutations(a, n);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// JavaScript program for above approach
function if_merged_permutations(a, n)
{
var pre_mex = Array(n).fill(0);
// Calculate the mex of the
// array a[0...i]
var freq = Array(n+1).fill(0);
for(var i = 0; i < n; i++)
{
pre_mex[i] = 1;
}
// Mex of empty
// array is 1
var mex = 1;
// Calculating the frequency
// of array elements
for(var i = 0; i < n; i++)
{
freq[a[i]]++;
if (freq[a[i]] > 1)
{
// In a permutation
// each element is
// present one time,
// So there is no chance
// of getting permutations
// for the prefix of
// length greater than i
break;
}
// The current element
// is the mex
if (a[i] == mex)
{
// While mex is present
// in the array
while (freq[mex] != 0)
{
mex++;
}
}
pre_mex[i] = mex;
}
var suf_mex = Array(n).fill(0);;
for(var i = 0; i < n; i++)
{
suf_mex[i] = 1;
}
// Calculate the mex of the
// array a[i..n]
freq = Array(n).fill(0);
// Mex of empty
// array is 1
mex = 1;
// Calculating the frequency
// of array elements
for(var i = n - 1; i > -1; i--)
{
freq[a[i]]++;
if (freq[a[i]] > 1)
{
// In a permutation each
// element is present
// one time, So there is
// no chance of getting
// permutations for the
// suffix of length lesser
// than i
continue;
}
// The current element is
// the mex
if (a[i] == mex)
{
// While mex is present
// in the array
while (freq[mex] != 0)
{
mex++;
}
}
suf_mex[i] = mex;
}
// Now check if there is atleast
// one index i such that mex of
// the prefix a[0..i]= i +
// 2(0 based indexing) and mex
// of the suffix a[i + 1..n]= n-i
for(var i = 0; i < n - 1; i++)
{
if (pre_mex[i] == i + 2 &&
suf_mex[i + 1] == n - i)
{
document.write("YES");
return;
}
}
document.write("NO");
}
// Driver Code
var a = [1, 3, 2, 4, 3, 1, 2];
var n = a.length;
if_merged_permutations(a, n);
</script>
Producción:
YES
Complejidad de tiempo: O(N)
Publicación traducida automáticamente
Artículo escrito por pedastrian y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA