Reduzca la array a un solo elemento eliminando repetidamente un elemento de cualquier par creciente

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:

  1. Elija un conjunto válido de índices en los que se pueda realizar la operación dada.
  2. 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 .
  3. 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>
Producción: 

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *