Dada una array arr[] que consiste en una permutación en el rango [1, N] , la tarea es verificar si la array dada se puede reducir a un solo elemento distinto de cero realizando las siguientes operaciones:
Seleccione los índices i y j tales que i < j y arr[i] < arr[j] y convierta uno de los dos elementos en 0 .
Si es posible reducir la array a un solo elemento, imprima «Sí» seguido de los índices elegidos junto con el índice del elemento reemplazado en cada operación. De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {2, 4, 6, 1, 3, 5}
Salida:
Si
0 1 1
0 2 2
3 4 3
0 4 4
0 5 5
Explicación:
En la primera operación elija los elementos 2 y 4 en índices 0 y 1. Convierta el elemento 4 en el índice 1 a 0, arr[] = {2, 0, 6, 1, 3, 5}
En la segunda operación elija los elementos 2 y 6 en los índices 0 y 2. Convierta el elemento 6 en el índice 2 a 0, arr[] = {2, 0, 0, 1, 3, 5}
En la tercera operación, elija los elementos 1 y 3 en los índices 3 y 4. Convierta el elemento 1 en el índice 3 a 0 , arr[] = {2, 0, 0, 0, 3, 5}
En la cuarta operación, elija los elementos 2 y 3 en los índices 0 y 4. Convierta el elemento 3 en el índice 4 a 0, arr[] = {2 , 0, 0, 0, 0, 5}
En la quinta operación, elija los elementos 2 y 5 en los índices 0 y 5. Convierta el elemento 5 en el índice 5 a 0, arr[] = {2, 0, 0, 0, 0, 0}
Entonces, la array se reduce a un solo elemento positivo en 5 operaciones.Entrada: arr[] = {2, 3, 1}
Salida: No
Explicación:
No hay un conjunto de operaciones en las que la array dada se pueda convertir en un solo elemento.
Enfoque: La idea es convertir todos los elementos de los índices [1, N – 2] primero a 0 y luego eliminar uno de los elementos 0 o (N – 1) en el último movimiento para obtener la array singleton . A continuación se muestran los pasos para resolver el problema:
- Elija un conjunto válido de índices en los que se pueda realizar la operación dada.
- Ahora, para elegir qué elemento convertir a 0 , verifique las siguientes condiciones:
- Si el índice 0 de la array es parte de estos índices, convierta el elemento en el otro índice a 0 .
- Si el índice 0 no es parte de los índices elegidos, reemplace el menor de los dos elementos a 0 .
- Continúe este proceso hasta que quede un solo elemento positivo en la array.
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 to print the order of
// indices of converted numbers
void order_of_removal(int a[], int n)
{
// Stores the values of indices
// with numbers > first index
queue<int> greater_indices;
int first = a[0];
// Stores the index of the closest
// consecutive number to index 0
int previous_index = 0;
// Push the indices into the queue
for (int i = 1; i < n; i++) {
if (a[i] > first)
greater_indices.push(i);
}
// Traverse the queue
while (greater_indices.size() > 0) {
// Stores the index of the
// closest number > arr[0]
int index = greater_indices.front();
greater_indices.pop();
int to_remove = index;
// Remove elements present in
// indices [1, to_remove - 1]
while (--to_remove > previous_index) {
cout << to_remove << " "
<< index << " "
<< to_remove << endl;
}
cout << 0 << " " << index << " "
<< index << endl;
// Update the previous_index
// to index
previous_index = index;
}
}
// Function to check if array arr[] can
// be reduced to single element or not
void canReduced(int arr[], int N)
{
// If array element can't be
// reduced to single element
if (arr[0] > arr[N - 1]) {
cout << "No" << endl;
}
// Otherwise find the order
else {
cout << "Yes" << endl;
order_of_removal(arr, N);
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
canReduced(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print the order of
// indices of converted numbers
public static void order_of_removal(int[] a, int n)
{
// Stores the values of indices
// with numbers > first index
Queue<Integer> greater_indices = new LinkedList<>();
int first = a[0];
// Stores the index of the closest
// consecutive number to index 0
int previous_index = 0;
// Push the indices into the queue
for(int i = 1; i < n; i++)
{
if (a[i] > first)
greater_indices.add(i);
}
// Traverse the queue
while (greater_indices.size() > 0)
{
// Stores the index of the
// closest number > arr[0]
int index = greater_indices.peek();
greater_indices.remove();
int to_remove = index;
// Remove elements present in
// indices [1, to_remove - 1]
while (--to_remove > previous_index)
{
System.out.println(to_remove + " " +
index + " " +
to_remove);
}
System.out.println(0 + " " + index +
" " + index);
// Update the previous_index
// to index
previous_index = index;
}
}
// Function to check if array arr[] can
// be reduced to single element or not
public static void canReduced(int[] arr, int N)
{
// If array element can't be
// reduced to single element
if (arr[0] > arr[N - 1])
{
System.out.println("No");
}
// Otherwise find the order
else
{
System.out.println("Yes");
order_of_removal(arr, N);
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4 };
int N = arr.length;
// Function call
canReduced(arr, N);
}
}
// This code is contributed divyeshrabadiya07
Python3
# Python3 program for the above approach
# Function to print the order of
# indices of converted numbers
def order_of_removal(a, n) :
# Stores the values of indices
# with numbers > first index
greater_indices = []
first = a[0]
# Stores the index of the closest
# consecutive number to index 0
previous_index = 0
# Push the indices into the queue
for i in range(1, n) :
if (a[i] > first) :
greater_indices.append(i)
# Traverse the queue
while (len(greater_indices) > 0) :
# Stores the index of the
# closest number > arr[0]
index = greater_indices[0];
greater_indices.pop(0)
to_remove = index
# Remove elements present in
# indices [1, to_remove - 1]
to_remove =- 1
while (to_remove > previous_index) :
print(to_remove, index, to_remove)
print(0, index, index)
# Update the previous_index
# to index
previous_index = index
# Function to check if array arr[] can
# be reduced to single element or not
def canReduced(arr, N) :
# If array element can't be
# reduced to single element
if (arr[0] > arr[N - 1]) :
print("No")
# Otherwise find the order
else :
print("Yes")
order_of_removal(arr, N)
# Given array arr[]
arr = [ 1, 2, 3, 4 ]
N = len(arr)
# Function Call
canReduced(arr, N)
# This code is contributed by divyesh072019
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print the order of
// indices of converted numbers
public static void order_of_removal(int[] a,
int n)
{
// Stores the values of indices
// with numbers > first index
Queue<int> greater_indices = new Queue<int>();
int first = a[0];
// Stores the index of the closest
// consecutive number to index 0
int previous_index = 0;
// Push the indices into the queue
for(int i = 1; i < n; i++)
{
if (a[i] > first)
greater_indices.Enqueue(i);
}
// Traverse the queue
while (greater_indices.Count > 0)
{
// Stores the index of the
// closest number > arr[0]
int index = greater_indices.Peek();
greater_indices.Dequeue();
int to_remove = index;
// Remove elements present in
// indices [1, to_remove - 1]
while (--to_remove > previous_index)
{
Console.WriteLine(to_remove + " " +
index + " " + to_remove);
}
Console.WriteLine(0 + " " + index +
" " + index);
// Update the previous_index
// to index
previous_index = index;
}
}
// Function to check if array []arr can
// be reduced to single element or not
public static void canReduced(int[] arr,
int N)
{
// If array element can't be
// reduced to single element
if (arr[0] > arr[N - 1])
{
Console.WriteLine("No");
}
// Otherwise find the order
else
{
Console.WriteLine("Yes");
order_of_removal(arr, N);
}
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = {1, 2, 3, 4};
int N = arr.Length;
// Function call
canReduced(arr, N);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for
// the above approach
// Function to print the order of
// indices of converted numbers
function order_of_removal(a, n) {
// Stores the values of indices
// with numbers > first index
var greater_indices = [];
var first = a[0];
// Stores the index of the closest
// consecutive number to index 0
var previous_index = 0;
// Push the indices into the queue
for (var i = 1; i < n; i++) {
if (a[i] > first) greater_indices.push(i);
}
// Traverse the queue
while (greater_indices.length > 0) {
// Stores the index of the
// closest number > arr[0]
var index = greater_indices[0];
greater_indices.shift();
var to_remove = index;
// Remove elements present in
// indices [1, to_remove - 1]
to_remove -= 1;
while (to_remove > previous_index) {
document.write(to_remove + " " + index + " " + to_remove + "<br>");
}
document.write(0 + " " + index + " " + index + "<br>");
// Update the previous_index
// to index
previous_index = index;
}
}
// Function to check if array []arr can
// be reduced to single element or not
function canReduced(arr, N) {
// If array element can't be
// reduced to single element
if (arr[0] > arr[N - 1]) {
document.write("No" + "<br>");
}
// Otherwise find the order
else {
document.write("Yes" + "<br>");
order_of_removal(arr, N);
}
}
// Driver Code
// Given array []arr
var arr = [1, 2, 3, 4];
var N = arr.length;
// Function call
canReduced(arr, N);
// This code is contributed by rdtank.
</script>
Yes 0 1 1 0 2 2 0 3 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por costheta_z y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA