Compruebe si todos los elementos de la array se pueden reducir a menos de X

Dada una array A[] que consta de N enteros positivos y un entero X , la tarea es determinar si es posible convertir todos los elementos de la array a menos de X realizando las siguientes operaciones:

• Seleccione 2 índices distintos j y k .
• Seleccione un índice i , donde A[i] > X .
• Reemplace A[i] = mcd(A[j], A[k]) si y solo si mcd (A[j], A[k]) ≠ 1.

Ejemplos: 

Entrada: A[] = {2, 1, 5, 3, 6}, X = 4  
Salida: Sí  
Explicación:

• Seleccionando i = 3, j = 4, k = 5, establezca A[i] = mcd(A[j], A[k]) = 3. Por lo tanto, A[] se modifica a {2, 1, 3, 3, 6}.
• Seleccionando i = 5, j = 4, k = 5, establezca A[i] = mcd(A[j], A[k]) = 3. Por lo tanto, A[] se modifica a {2, 1, 3, 3, 3}.

Entrada: A[] = {2, 3, 2, 5, 4}, X = 3 
Salida: Sí

Enfoque: siga los pasos a continuación para resolver el problema: 

1. Encuentre los dos números que tienen mcd ≠ 1 así como mcd ≤ X , luego, usando estos dos números, el número requerido A[i] se puede reemplazar con mcd(A[j], A[k]) .
2. Usando el hecho de que mcd(x, y) ≤ min(x, y) , los elementos de la array se pueden reducir a ≤ X .
3. De esta manera, el resto de la array se puede convertir a ≤ X usando el paso 2 .

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

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if all array
// elements are≤ X
bool check(int A[], int X, int N)
{
    for(int i = 0; i < N; i++)
    {
        if (A[i] > X)
        {
            return false;
        }
    }
    return true;
}
 
// Function to check if all array elements
// can be reduced to less than X or not
bool findAns(int A[], int N, int X)
{
     
    // Checks if all array elements
    // are already ≤ X or not
    if (check(A, X, N))
    {
        return true;
    }
 
    // Traverse every possible pair
    for(int i = 0; i < N; i++)
    {
        for(int j = i + 1; j < N; j++)
        {
             
            // Calculate GCD of two
            // array elements
            int g = __gcd(A[i], A[j]);
 
            // If gcd is ≠ 1
            if (g != 1)
            {
                 
                // If gcd is ≤ X, then a pair
                // is present to reduce all
                // array elements to ≤ X
                if (g <= X)
                {
                    return true;
                }
            }
        }
    }
     
    // If no pair is present
    // with gcd is ≤ X
    return false;
}
 
// Driver Code
int main()
{
    int X = 4;
    int A[] = { 2, 1, 5, 3, 6 };
    int N = 5;
     
    if (findAns(A, N, X))
    {
        cout << "true";
    }
    else
    {
        cout << "false";
    }
}
 
// This code is contributed by mohit kumar 29

// Java Program to implement
// the above approach
 
import java.io.*;
import java.util.Arrays;
 
class GFG {
 
    // Function to check if all array elements
    // can be reduced to less than X or not
    public static boolean findAns(
        int[] A, int N, int X)
    {
        // Checks if all array elements
        // are already ≤ X or not
        if (check(A, X)) {
            return true;
        }
 
        // Traverse every possible pair
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
 
                // Calculate GCD of two
                // array elements
                int gcd = gcd(A[i], A[j]);
 
                // If gcd is ≠ 1
                if (gcd != 1) {
 
                    // If gcd is ≤ X, then a pair
                    // is present to reduce all
                    // array elements to ≤ X
                    if (gcd <= X) {
 
                        return true;
                    }
                }
            }
        }
 
        // If no pair is present
        // with gcd is ≤ X
        return false;
    }
 
    // Function to check if all array elements are≤ X
    public static boolean check(int[] A, int X)
    {
        for (int i = 0; i < A.length; i++) {
            if (A[i] > X) {
                return false;
            }
        }
        return true;
    }
 
    // Function to calculate gcd of two numbers
    public static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int X = 4;
        int[] A = { 2, 1, 5, 3, 6 };
        int N = 5;
 
        System.out.println(findAns(A, N, X));
    }
}

# Python3 program to implement
# the above approach
 
# Function to check if all array elements
# can be reduced to less than X or not
def findAns(A, N, X):
   
  # Checks if all array elements
  # are already ≤ X or not
  if (check(A, X)):
    return True
         
  # Traverse every possible pair
  for i in range(N):
    for j in range(i + 1, N):
       
      # Calculate GCD of two
      # array elements
      gcd = GCD(A[i], A[j])
 
      # If gcd is ≠ 1
      if (gcd != 1):
         
        # If gcd is ≤ X, then a pair
        # is present to reduce all
        # array elements to ≤ X
        if (gcd <= X):
          return True
 
  # If no pair is present
  # with gcd is ≤ X
  return False
 
# Function to check if all array elements are≤ X
def check(A, X):
  for i in range(len(A)):
    if (A[i] > X):
      return False
  return True
 
# Function to calculate gcd of two numbers
def GCD(a, b):
  if (b == 0):
    return a
  return GCD(b, a % b)
 
# Driver Code
X = 4
A = [ 2, 1, 5, 3, 6 ]
N = 5
 
print(findAns(A, N, X))
 
# This code is contributed by rohitsingh07052

// C# Program to implement
// the above approach
using System;
class GFG {
 
    // Function to check if all array elements
    // can be reduced to less than X or not
    public static bool findAns(
        int[] A, int N, int X)
    {
        // Checks if all array elements
        // are already ≤ X or not
        if (check(A, X))
        {
            return true;
        }
 
        // Traverse every possible pair
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
 
                // Calculate GCD of two
                // array elements
                int gcd = gcdFoo(A[i], A[j]);
 
                // If gcd is ≠ 1
                if (gcd != 1)
                {
 
                    // If gcd is ≤ X, then a pair
                    // is present to reduce all
                    // array elements to ≤ X
                    if (gcd <= X)
                    {
                        return true;
                    }
                }
            }
        }
 
        // If no pair is present
        // with gcd is ≤ X
        return false;
    }
 
    // Function to check if all array elements are≤ X
    public static bool check(int[] A, int X)
    {
        for (int i = 0; i < A.Length; i++)
        {
            if (A[i] > X)
            {
                return false;
            }
        }
        return true;
    }
 
    // Function to calculate gcd of two numbers
    static int gcdFoo(int a, int b)
    {
        if (b == 0)
            return a;
        return gcdFoo(b, a % b);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int X = 4;
        int[] A = { 2, 1, 5, 3, 6 };
        int N = 5;
 
        Console.WriteLine(findAns(A, N, X));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
// javascript program of the above approach
 
    // Function to check if all array elements
    // can be reduced to less than X or not
    function findAns(
         A, N, X)
    {
        // Checks if all array elements
        // are already ≤ X or not
        if (check(A, X)) {
            return true;
        }
  
        // Traverse every possible pair
        for (let i = 0; i < N; i++) {
            for (let j = i + 1; j < N; j++) {
  
                // Calculate GCD of two
                // array elements
                let gcdd = gcd(A[i], A[j]);
  
                // If gcd is ≠ 1
                if (gcdd != 1) {
  
                    // If gcd is ≤ X, then a pair
                    // is present to reduce all
                    // array elements to ≤ X
                    if (gcdd <= X) {
  
                        return true;
                    }
                }
            }
        }
  
        // If no pair is present
        // with gcd is ≤ X
        return false;
    }
  
    // Function to check if all array elements are≤ X
    function check(A, X)
    {
        for (let i = 0; i < A.length; i++) {
            if (A[i] > X) {
                return false;
            }
        }
        return true;
    }
  
    // Function to calculate gcd of two numbers
    function gcd(a, b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
  
 
    // Driver Code
     
        let X = 4;
        let A = [ 2, 1, 5, 3, 6 ];
        let N = 5;
  
        document.write(findAns(A, N, X));
 
// This code is contributed by target_2.
</script>

true

 Complejidad de Tiempo: O(N ² ) 
Espacio Auxiliar: O(1)