Dada una array freq[] que almacena la frecuencia de N enteros de 0 a N – 1 . La tarea es construir una secuencia donde el número i aparece freq[i] número de veces (0 ≤ i ≤ N – 1) tal que la diferencia absoluta entre dos números adyacentes sea 1. Si no es posible generar ninguna secuencia, imprima – 1 .
Ejemplos:
Entrada: freq[] = {2, 2, 2, 3, 1}
Salida: 0 1 0 1 2 3 2 3 4 3
Explicación:
La diferencia absoluta entre los números adyacentes en la secuencia anterior es siempre 1.Entrada: freq[] = {1, 2, 3}
Salida: -1
Explicación:
No puede haber ninguna secuencia cuya diferencia absoluta sea siempre uno.
Enfoque: La secuencia puede comenzar desde cualquier número entre 0 y N – 1 . La idea es considerar todas las posibilidades para los elementos iniciales, es decir, 0 a N – 1 . Después de elegir el elemento, tratamos de construir la secuencia. A continuación se muestran los pasos:
- Crea un mapa M para almacenar la frecuencia de los números. Además, encuentre la suma de frecuencias en una variable, digamos total .
- Iterar en el mapa y hacer lo siguiente para cada elemento del mapa:
- Cree una copia del mapa M .
- Cree una secuencia de vectores que almacene la posible respuesta. Si la frecuencia del elemento actual no es cero, disminuya su frecuencia e introdúzcalo en la secuencia e intente formar el resto del total – 1 elementos de la secuencia de la siguiente manera:
- Llamemos último al último elemento insertado en la secuencia . Si la frecuencia del último – 1 no es cero, entonces disminuya su frecuencia y empújelo a la secuencia . Actualiza el último elemento.
- De lo contrario, si la frecuencia del último + 1 no es cero, disminuya su frecuencia y empújela a la secuencia . Actualiza el último elemento.
- De lo contrario, rompa el bucle interior.
- Si el tamaño de la secuencia es igual al total , devuélvelo como la respuesta.
- Si no se encuentra tal secuencia, simplemente devuelva una secuencia vacía.
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;
// Function generates the sequence
vector<int> generateSequence(int* freq,
int n)
{
// Map to store the frequency
// of numbers
map<int, int> m;
// Sum of all frequencies
int total = 0;
for (int i = 0; i < n; i++) {
m[i] = freq[i];
total += freq[i];
}
// Try all possibilities
// for the starting element
for (int i = 0; i < n; i++) {
// If the frequency of current
// element is non-zero
if (m[i]) {
// vector to store the answer
vector<int> sequence;
// Copy of the map for every
// possible starting element
auto mcopy = m;
// Decrement the frequency
mcopy[i]--;
// Push the starting element
// to the vector
sequence.push_back(i);
// The last element inserted
// is i
int last = i;
// Try to fill the rest of
// the positions if possible
for (int i = 0;
i < total - 1; i++) {
// If the frequency of last - 1
// is non-zero
if (mcopy[last - 1]) {
// Decrement the frequency
// of last - 1
mcopy[last - 1]--;
// Insert it into the
// sequence
sequence.push_back(last - 1);
// Update last number
// added to sequence
last--;
}
else if (mcopy[last + 1]) {
mcopy[last + 1]--;
sequence.push_back(last + 1);
last++;
}
// Break from the inner loop
else
break;
}
// If the size of the sequence
// vector is equal to sum of
// total frequqncies
if (sequence.size() == total) {
// Return sequence
return sequence;
}
}
}
vector<int> empty;
// If no such sequence if found
// return empty sequence
return empty;
}
// Function Call to print the sequence
void PrintSequence(int freq[], int n)
{
// The required sequence
vector<int> sequence
= generateSequence(freq, n);
// If the size of sequence
// if zero it means no such
// sequence was found
if (sequence.size() == 0) {
cout << "-1";
}
// Otherwise print the sequence
else {
for (int i = 0;
i < sequence.size(); i++) {
cout << sequence[i] << " ";
}
}
}
// Driver Code
int main()
{
// Frequency of all elements
// from 0 to n-1
int freq[] = { 2, 2, 2, 3, 1 };
// Number of elements whose
// frequencies are given
int N = 5;
// Function Call
PrintSequence(freq, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function generates the sequence
static Vector<Integer> generateSequence(int []freq,
int n)
{
// Map to store the frequency
// of numbers
HashMap<Integer,
Integer> m = new HashMap<Integer,
Integer>();
// Sum of all frequencies
int total = 0;
for(int i = 0; i < n; i++)
{
m.put(i, freq[i]);
total += freq[i];
}
// Try all possibilities
// for the starting element
for(int i = 0; i < n; i++)
{
// If the frequency of current
// element is non-zero
if (m.containsKey(i))
{
// vector to store the answer
Vector<Integer> sequence = new Vector<Integer>();
// Copy of the map for every
// possible starting element
@SuppressWarnings("unchecked")
HashMap<Integer,
Integer> mcopy = (HashMap<Integer,
Integer>) m.clone();
// Decrement the frequency
if (mcopy.containsKey(i) && mcopy.get(i) > 0)
mcopy.put(i, mcopy.get(i) - 1);
// Push the starting element
// to the vector
sequence.add(i);
// The last element inserted
// is i
int last = i;
// Try to fill the rest of
// the positions if possible
for(int i1 = 0; i1 < total - 1; i1++)
{
// If the frequency of last - 1
// is non-zero
if (mcopy.containsKey(last - 1) &&
mcopy.get(last - 1) > 0)
{
// Decrement the frequency
// of last - 1
mcopy.put(last - 1,
mcopy.get(last - 1) - 1);
// Insert it into the
// sequence
sequence.add(last - 1);
// Update last number
// added to sequence
last--;
}
else if (mcopy.containsKey(last + 1))
{
mcopy.put(last + 1,
mcopy.get(last + 1) - 1);
sequence.add(last + 1);
last++;
}
// Break from the inner loop
else
break;
}
// If the size of the sequence
// vector is equal to sum of
// total frequqncies
if (sequence.size() == total)
{
// Return sequence
return sequence;
}
}
}
Vector<Integer> empty = new Vector<Integer>();
// If no such sequence if found
// return empty sequence
return empty;
}
// Function call to print the sequence
static void PrintSequence(int freq[], int n)
{
// The required sequence
Vector<Integer> sequence = generateSequence(freq, n);
// If the size of sequence
// if zero it means no such
// sequence was found
if (sequence.size() == 0)
{
System.out.print("-1");
}
// Otherwise print the sequence
else
{
for(int i = 0; i < sequence.size(); i++)
{
System.out.print(sequence.get(i) + " ");
}
}
}
// Driver Code
public static void main(String[] args)
{
// Frequency of all elements
// from 0 to n-1
int freq[] = { 2, 2, 2, 3, 1 };
// Number of elements whose
// frequencies are given
int N = 5;
// Function call
PrintSequence(freq, N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
# Function generates the sequence
def generateSequence(freq, n):
# Map to store the frequency
# of numbers
m = {}
# Sum of all frequencies
total = 0
for i in range(n):
m[i] = freq[i]
total += freq[i]
# Try all possibilities
# for the starting element
for i in range(n):
# If the frequency of current
# element is non-zero
if (m[i]):
# vector to store the answer
sequence = []
# Copy of the map for every
# possible starting element
mcopy = {}
for j in m:
mcopy[j] = m[j]
# Decrement the frequency
mcopy[i] -= 1
# Push the starting element
# to the vector
sequence.append(i)
# The last element inserted
# is i
last = i
# Try to fill the rest of
# the positions if possible
for j in range(total - 1):
# If the frequency of last - 1
# is non-zero
if ((last - 1) in mcopy and
mcopy[last - 1] > 0):
# Decrement the frequency
# of last - 1
mcopy[last - 1] -= 1
# Insert it into the
# sequence
sequence.append(last - 1)
# Update last number
# added to sequence
last -= 1
elif (mcopy[last + 1]):
mcopy[last + 1] -= 1
sequence.append(last + 1)
last += 1
# Break from the inner loop
else:
break
# If the size of the sequence
# vector is equal to sum of
# total frequqncies
if (len(sequence) == total):
# Return sequence
return sequence
# If no such sequence if found
# return empty sequence
return []
# Function Call to print the sequence
def PrintSequence(freq, n):
# The required sequence
sequence = generateSequence(freq, n)
# If the size of sequence
# if zero it means no such
# sequence was found
if (len(sequence) == 0):
print("-1")
# Otherwise print the sequence
else:
for i in range(len(sequence)):
print(sequence[i], end = " ")
# Driver Code
if __name__ == '__main__':
# Frequency of all elements
# from 0 to n-1
freq = [ 2, 2, 2, 3, 1 ]
# Number of elements whose
# frequencies are given
N = 5
# Function Call
PrintSequence(freq, N)
# This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function generates the sequence
static List<int> generateSequence(int []freq,
int n)
{
// Map to store the frequency
// of numbers
Dictionary<int,
int> m = new Dictionary<int,
int>();
// Sum of all frequencies
int total = 0;
for(int i = 0; i < n; i++)
{
m.Add(i, freq[i]);
total += freq[i];
}
// Try all possibilities
// for the starting element
for(int i = 0; i < n; i++)
{
// If the frequency of current
// element is non-zero
if (m.ContainsKey(i))
{
// vector to store the answer
List<int> sequence = new List<int>();
// Copy of the map for every
// possible starting element
Dictionary<int,
int> mcopy = new Dictionary<int,
int>(m);
// Decrement the frequency
if (mcopy.ContainsKey(i) && mcopy[i] > 0)
mcopy[i] = mcopy[i] - 1;
// Push the starting element
// to the vector
sequence.Add(i);
// The last element inserted
// is i
int last = i;
// Try to fill the rest of
// the positions if possible
for(int i1 = 0; i1 < total - 1; i1++)
{
// If the frequency of last - 1
// is non-zero
if (mcopy.ContainsKey(last - 1) &&
mcopy[last - 1] > 0)
{
// Decrement the frequency
// of last - 1
mcopy[last - 1] = mcopy[last - 1] - 1;
// Insert it into the
// sequence
sequence.Add(last - 1);
// Update last number
// added to sequence
last--;
}
else if (mcopy.ContainsKey(last + 1))
{
mcopy[last + 1] = mcopy[last + 1] - 1;
sequence.Add(last + 1);
last++;
}
// Break from the inner loop
else
break;
}
// If the size of the sequence
// vector is equal to sum of
// total frequqncies
if (sequence.Count == total)
{
// Return sequence
return sequence;
}
}
}
List<int> empty = new List<int>();
// If no such sequence if found
// return empty sequence
return empty;
}
// Function call to print the sequence
static void PrintSequence(int []freq, int n)
{
// The required sequence
List<int> sequence = generateSequence(freq, n);
// If the size of sequence
// if zero it means no such
// sequence was found
if (sequence.Count == 0)
{
Console.Write("-1");
}
// Otherwise print the sequence
else
{
for(int i = 0; i < sequence.Count; i++)
{
Console.Write(sequence[i] + " ");
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Frequency of all elements
// from 0 to n-1
int []freq = {2, 2, 2, 3, 1};
// Number of elements whose
// frequencies are given
int N = 5;
// Function call
PrintSequence(freq, N);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function generates the sequence
function generateSequence(freq, n)
{
// Map to store the frequency
// of numbers
let m = new Map();
// Sum of all frequencies
let total = 0;
for(let i = 0; i < n; i++)
{
m.set(i, freq[i]);
total += freq[i];
}
// Try all possibilities
// for the starting element
for(let i = 0; i < n; i++)
{
// If the frequency of current
// element is non-zero
if (m.has(i))
{
// vector to store the answer
let sequence = [];
// Copy of the map for every
// possible starting element
let mcopy = new Map();
for(let [key, value] of m.entries())
{
mcopy.set(key,value);
}
// Decrement the frequency
if (mcopy.has(i) && mcopy.get(i) > 0)
mcopy.set(i, mcopy.get(i) - 1);
// Push the starting element
// to the vector
sequence.push(i);
// The last element inserted
// is i
let last = i;
// Try to fill the rest of
// the positions if possible
for(let i1 = 0; i1 < total - 1; i1++)
{
// If the frequency of last - 1
// is non-zero
if (mcopy.has(last - 1) &&
mcopy.get(last - 1) > 0)
{
// Decrement the frequency
// of last - 1
mcopy.set(last - 1,
mcopy.get(last - 1) - 1);
// Insert it into the
// sequence
sequence.push(last - 1);
// Update last number
// added to sequence
last--;
}
else if (mcopy.has(last + 1))
{
mcopy.set(last + 1,
mcopy.get(last + 1) - 1);
sequence.push(last + 1);
last++;
}
// Break from the inner loop
else
break;
}
// If the size of the sequence
// vector is equal to sum of
// total frequqncies
if (sequence.length == total)
{
// Return sequence
return sequence;
}
}
}
let empty = [];
// If no such sequence if found
// return empty sequence
return empty;
}
// Function call to print the sequence
function PrintSequence(freq, n)
{
// The required sequence
let sequence = generateSequence(freq, n);
// If the size of sequence
// if zero it means no such
// sequence was found
if (sequence.length == 0)
{
document.write("-1");
}
// Otherwise print the sequence
else
{
for(let i = 0; i < sequence.length; i++)
{
document.write(sequence[i] + " ");
}
}
}
// Driver Code
// Frequency of all elements
// from 0 to n-1
let freq = [ 2, 2, 2, 3, 1 ];
// Number of elements whose
// frequencies are given
let N = 5;
// Function call
PrintSequence(freq, N);
// This code is contributed by unknown2108
</script>
Producción:
0 1 0 1 2 3 2 3 4 3
Complejidad de tiempo: O(N * total) , donde N es el tamaño de la array y el total es la suma acumulativa de la array.
Espacio auxiliar: O(total) , donde el total es la suma acumulada de la array.
Publicación traducida automáticamente
Artículo escrito por mohitkumarbt2k18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA