Encuentre N-1 pares (X, Y) de una array dada de modo que X e Y sean diferentes y X módulo Y no esté presente en la array

Dada una array Arr[] de tamaño N que consta de N enteros positivos distintos por pares. La tarea es encontrar N – 1 par diferente de enteros positivos X, Y que satisfagan las siguientes condiciones: 

• X ≠ Y
• X, Y ambos pertenecen a la array.
• X mod Y no pertenece a la array.

Nota: Se demuestra que siempre existen N-1 tales pares.

Ejemplos:

Entrada: N = 4 , Arr [ ] = { 2 , 3 ,4 ,5 }
Salida: (5 , 2) , (4 , 2) , (3 , 2)
Explicación: 4 – 1 = 3, por lo tanto, 3 pares impreso. 
En el primer par 5 y 2 ambos pertenecen al arreglo, 5 no es igual a 2, 5 mod 2 no pertenece al arreglo. 
Lo mismo es aplicable para todos los pares impresos.

Entrada: N = 2, Arr [ ] = { 1 , 3 }
Salida: 3 , 1
Explicación:  2 – 1 = 1. Por lo tanto, solo existe uno de esos pares. Eso es 3, 1.

Enfoque: El problema anterior se puede resolver usando el método Greedy . En este enfoque, nunca busque todos los casos posibles. En cambio, busca la parte o cantidad que necesitamos. Siga los pasos a continuación para resolver este problema: 

• Inicialice la variable min_element como Arr[0].
• Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
  • Calcule el valor de min_element como el elemento mínimo de la array Arr[].
• Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
  • Si Arr[i] no es igual a min_element,  imprima Arr[i], min_element como el par.

Este enfoque se basa en la siguiente observación:

Digamos que X es el elemento mínimo en la array dada. 
El valor Arr[i] % X siempre será menor que X y ningún elemento en la array es menor que X

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 find the possible pairs
void find(int N, int Arr[])
{
    int min_element = Arr[0];
 
    // Get the minimum element
    for (int i = 0; i < N; i++) {
        if (Arr[i] < min_element) {
            min_element = Arr[i];
        }
    }
 
    // Pair rest N - 1 elements with
    // the minimum element and print
    for (int i = 0; i < N; i++) {
        if (Arr[i] != min_element) {
            cout << Arr[i] << " " <<
                min_element << endl;
        }
    }
}
 
// Driver Code
int main()
{
 
    // Initialize N and the Array
    int N = 4;
    int Arr[4] = { 2, 3, 4, 5 };
 
    find(N, Arr);
 
    return 0;
}

// Java  program for the above approach
import java.util.*;
public class GFG
{
   
// Function to find the possible pairs
static void find(int N, int Arr[])
{
    int min_element = Arr[0];
 
    // Get the minimum element
    for (int i = 0; i < N; i++) {
        if (Arr[i] < min_element) {
            min_element = Arr[i];
        }
    }
 
    // Pair rest N - 1 elements with
    // the minimum element and print
    for (int i = 0; i < N; i++) {
        if (Arr[i] != min_element) {
            System.out.println(Arr[i] + " " +
                min_element);
        }
    }
}
 
// Driver Code
public static void main(String args[])
{
    int N = 4;
    int Arr[] = { 2, 3, 4, 5 };
 
    find(N, Arr);
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

# python3 program for the above approach
 
# Function to find the possible pairs
def find(N, Arr):
 
    min_element = Arr[0]
 
    # Get the minimum element
    for i in range(0, N):
        if (Arr[i] < min_element):
            min_element = Arr[i]
 
    # Pair rest N - 1 elements with
    # the minimum element and print
    for i in range(0, N):
        if (Arr[i] != min_element):
            print(f"{Arr[i]} {min_element}")
 
# Driver Code
if __name__ == "__main__":
 
    # Initialize N and the Array
    N = 4
    Arr = [2, 3, 4, 5]
 
    find(N, Arr)
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG
{
   
// Function to find the possible pairs
static void find(int N, int []Arr)
{
    int min_element = Arr[0];
 
    // Get the minimum element
    for (int i = 0; i < N; i++) {
        if (Arr[i] < min_element) {
            min_element = Arr[i];
        }
    }
 
    // Pair rest N - 1 elements with
    // the minimum element and print
    for (int i = 0; i < N; i++) {
        if (Arr[i] != min_element) {
            Console.WriteLine(Arr[i] + " " +
                min_element);
        }
    }
}
 
// Driver Code
public static void Main()
{
    int N = 4;
    int []Arr = { 2, 3, 4, 5 };
 
    find(N, Arr);
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
// Javascript program for the above approach
 
// Function to find the possible pairs
function find(N, Arr)
{
     
    let min_element = Arr[0];
 
    // Get the minimum element
    for (let i = 0; i < N; i++) {
        if (Arr[i] < min_element) {
            min_element = Arr[i];
        }
    }
 
    // Pair rest N - 1 elements with
    // the minimum element and print
    for (let i = 0; i < N; i++) {
        if (Arr[i] != min_element) {
            document.write(Arr[i] + " " +
                min_element);
        }
    }
}
 
// Driver Code
// Initialize N and the Array
let N = 4;
let Arr = [ 2, 3, 4, 5 ];
 
find(N, Arr);
 
// This code is contributed by Samim Hossain Mondal.
</script>

3 2
4 2
5 2

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