Ordene la array eligiendo los índices i, j, k y reemplazando arr[i] con arr[j] – arr[k]

Dada una array arr[] de N enteros, la tarea es ordenar la array reemplazando cualquier elemento en el índice i ( arr[i] ) con arr[j] – arr[k] tal que i < j < k .

Nota: Si no se necesita ninguna operación, imprima 0.

Ejemplos:

Entrada: arr[] = {2, -2, -3, -1, 3}
Salida:
3
3 4 5
2 4 5
1 4 5
Explicación: El número en la 3ra posición puede ser reemplazado por la 4ta y última posición. 
La array se convierte en {2, -2, -4, -1, 3}. Entonces 31, 4, 5}
El número en la segunda posición puede ser reemplazado por la cuarta y última posición. 
La array se convierte en {2, -4, -4, -1, 3}. Entonces {2, 4, 5}
El número en la primera posición puede ser reemplazado por la cuarta y última posición. 
La array se convierte en {-4, -4, -4, -1, 3}. Entonces {1, 4, 5}
Array se ordena después de 3 reemplazos, por lo que 3 se imprime al principio.

Entrada: arr[] = {1, 2, -3, -5}
Salida: -1 
Explicación: La array nunca se puede ordenar mediante las siguientes operaciones.

Enfoque: El enfoque se basa en el hecho de que: 

Los dos últimos elementos nunca pueden efectuarse ya que la necesidad es seleccionar 3 índices e i < j < k. Entonces, el reemplazo por la diferencia entre los dos últimos elementos hace que la array esté ordenada si los dos últimos están ordenados.

Aquí están los casos que vienen:
Caso-1: Si arr[N-1] >= 0 y si el arreglo no está ordenado, los elementos del índice i = [0, N – 3] pueden ser reemplazados por arr[N – 2] – arr[N-1] ya que i < j < k y la diferencia arr[N – 2] – arr[N-1] será menor que a[N – 2].

Caso-2: Si arr[N-1] < 0 no es posible ordenar el arreglo por reemplazos.
Si los dos últimos elementos arr[N – 1], arr[N-2] están ordenados pero a[N-1] < 0, entonces si se elige algún índice i
arr[i] = arr[N-2] – (- a[N-1]), esto se convierte en > a[N – 1], lo que viola la propiedad de clasificación, así que NO.

Caso 3: si los dos últimos elementos no están ordenados, la clasificación no es posible porque no podemos modificar los dos últimos elementos de ninguna manera.

Siga estos pasos para resolver el problema anterior:

• Compruebe si los dos últimos elementos están ordenados o no, ya que no se pueden realizar operaciones en ellos.
• Si el último elemento arr[N – 1] es mayor o igual a 0, reemplace los índices [0, N – 3] con arr[N – 2] – arr[N-1].
• Si el último elemento es negativo, no se puede ordenar, si inicialmente no se clasificó. Así que compruebe si la array se ordenó o no.

A continuación se muestra la implementación del enfoque anterior.

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the array
// can be sorted with replacements
void is_possible(int arr[], int n)
{
 
    // Check for the last two elements
    // if they are sorted or not
    // If they are not sorted print No
    if (arr[n - 2] > arr[n - 1]) {
        cout << "-1" << endl;
        return;
    }
 
    // If last element is greater than
    // or equal to 0 then elements index
    // [0, n-3] can be replaced by
    // a[n - 2] - a[n - 1] and it is
    // possible to sort the array
    if (arr[n - 1] >= 0) {
        cout << n - 2 << "\n";
        for (int i = 0; i <= n - 3; i++) {
            cout << i + 1 << " " << n - 1
                 << " " << n << endl;
        }
    }
 
    // If arr[n-1] is negative,
    // it not possible except in case
    // the whole array is initially
    // negative sorted
    else {
 
        // Check if the array is sorted
        for (int i = 0; i < n - 2; i++) {
            if (arr[i] > arr[i + 1]) {
                cout << "-1" << endl;
                return;
            }
        }
 
        // If the array is initially sorted
        cout << "0" << endl;
    }
}
 
// Driver code
int main()
{
    int arr[] = { 2, -2, -3, -1, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    is_possible(arr, N);
    return 0;
}

// JAVA program for the above approach
import java.util.*;
class GFG
{
 
  // Function to check if the array
  // can be sorted with replacements
  public static void is_possible(int arr[], int n)
  {
 
    // Check for the last two elements
    // if they are sorted or not
    // If they are not sorted print No
    if (arr[n - 2] > arr[n - 1]) {
      System.out.println("-1");
      return;
    }
 
    // If last element is greater than
    // or equal to 0 then elements index
    // [0, n-3] can be replaced by
    // a[n - 2] - a[n - 1] and it is
    // possible to sort the array
    if (arr[n - 1] >= 0) {
      System.out.println(n - 2);
      for (int i = 0; i <= n - 3; i++) {
        System.out.print(i + 1 + " ");
        System.out.print(n - 1 + " ");
        System.out.print(n);
        System.out.println();
      }
    }
 
    // If arr[n-1] is negative,
    // it not possible except in case
    // the whole array is initially
    // negative sorted
    else {
 
      // Check if the array is sorted
      for (int i = 0; i < n - 2; i++) {
        if (arr[i] > arr[i + 1]) {
          System.out.println("-1");
          return;
        }
      }
 
      // If the array is initially sorted
      System.out.println("0");
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int arr[] = new int[] { 2, -2, -3, -1, 3 };
    int N = arr.length;
 
    // Function call
    is_possible(arr, N);
  }
}
 
// This code is contributed by Taranpreet

# Python program for the above approach
 
# Function to check if the array
# can be sorted with replacements
def is_possible(arr, n):
 
    # Check for the last two elements
    # if they are sorted or not
    # If they are not sorted print No
    if (arr[n - 2] > arr[n - 1]):
        print(-1)
        return
 
    # If last element is greater than
    # or equal to 0 then elements index
    # [0, n-3] can be replaced by
    # a[n - 2] - a[n - 1] and it is
    # possible to sort the array
    if (arr[n - 1] >= 0):
        print(n - 2)
        for i in range(0, n - 2):
            print(i + 1, n - 1, n)
 
    # If arr[n-1] is negative,
    # it not possible except in case
    # the whole array is initially
    # negative sorted
    else:
       
      # Check if the array is sorted
      for i in range(0, n - 2):
         if (arr[i] > arr[i + 1]):
            print("-1")
            return
 
      # If the array is initially sorted
      print("0")
 
# Driver code
if __name__ == "__main__":
               
    arr = [ 2, -2, -3, -1, 3 ]
    N = len(arr)
 
    # Function call
    is_possible(arr, N)
     
    # This code is contributed by hrithikgarg03188.

// C# program for the above approach
using System;
class GFG {
 
  // Function to check if the array
  // can be sorted with replacements
  static void is_possible(int[] arr, int n)
  {
 
    // Check for the last two elements
    // if they are sorted or not
    // If they are not sorted print No
    if (arr[n - 2] > arr[n - 1]) {
      Console.WriteLine("-1");
      return;
    }
 
    // If last element is greater than
    // or equal to 0 then elements index
    // [0, n-3] can be replaced by
    // a[n - 2] - a[n - 1] and it is
    // possible to sort the array
    if (arr[n - 1] >= 0) {
      Console.WriteLine(n - 2);
      for (int i = 0; i <= n - 3; i++) {
        Console.WriteLine((i + 1) + " " + (n - 1)
                          + " " + n);
      }
    }
 
    // If arr[n-1] is negative,
    // it not possible except in case
    // the whole array is initially
    // negative sorted
    else {
 
      // Check if the array is sorted
      for (int i = 0; i < n - 2; i++) {
        if (arr[i] > arr[i + 1]) {
          Console.WriteLine(-1);
          return;
        }
      }
 
      // If the array is initially sorted
      Console.WriteLine("0");
    }
  }
 
  // Driver code
  public static void Main()
  {
    int[] arr = { 2, -2, -3, -1, 3 };
    int N = arr.Length;
 
    // Function call
    is_possible(arr, N);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript program for the above approach
 
    // Function to check if the array
    // can be sorted with replacements
    const is_possible = (arr, n) => {
 
        // Check for the last two elements
        // if they are sorted or not
        // If they are not sorted print No
        if (arr[n - 2] > arr[n - 1]) {
            document.write("-1<br/>");
            return;
        }
 
        // If last element is greater than
        // or equal to 0 then elements index
        // [0, n-3] can be replaced by
        // a[n - 2] - a[n - 1] and it is
        // possible to sort the array
        if (arr[n - 1] >= 0) {
            document.write(`${n - 2}<br/>`);
            for (let i = 0; i <= n - 3; i++) {
                document.write(`${i + 1} ${n - 1} ${n}<br/>`);
            }
        }
 
        // If arr[n-1] is negative,
        // it not possible except in case
        // the whole array is initially
        // negative sorted
        else {
 
            // Check if the array is sorted
            for (let i = 0; i < n - 2; i++) {
                if (arr[i] > arr[i + 1]) {
                    document.write("-1<br/>");
                    return;
                }
            }
 
            // If the array is initially sorted
            document.write("0<br/>");
        }
    }
 
    // Driver code
    let arr = [2, -2, -3, -1, 3];
    let N = arr.length;
 
    // Function call
    is_possible(arr, N);
 
// This code is contributed by rakeshsahni
 
</script>

3
1 4 5
2 4 5
3 4 5

Complejidad temporal: O(N)
Espacio auxiliar: O(1)