Dada una array arr[] que consta de N elementos, la tarea es minimizar la longitud de la array reemplazando dos elementos coprimos cualesquiera de la array con 1 .
Ejemplos:
Entrada: arr[] = {2, 3, 5}
Salida: 1
Explicación:
Reemplazar {2, 3} con 1 modifica la array a {1, 5}.
Reemplazar {1, 5} con 1 modifica la array a {1}.
Entrada: arr[] = {6, 9, 15}
Salida: 3
Explicación: No existen pares coprimos en la array. Por lo tanto, no hay reducción posible.
Enfoque ingenuo: el enfoque más simple es iterar sobre la array y verificar los pares coprimos. Si lo encuentra, reemplácelo con 1, busque el siguiente par coprimo y así sucesivamente.
Complejidad de Tiempo: O(N 3 * logN)
Espacio Auxiliar: O(1)
Enfoque eficiente: este enfoque se basa en el hecho de que:
1 es coprimo con todos los números
La idea es encontrar si hay algún par coprimo presente en la array o no. Si se encuentra, todos los elementos de la array se pueden reducir a 1 en función del hecho anterior. Por lo tanto, si se encuentra algún par coprimo, la respuesta requerida será 1, de lo contrario, la respuesta será el tamaño inicial de la array.
Ilustración:
Para arr[] = {2, 4, 6, 8, 9}
Aquí, como existe un par coprimo {2, 9}, reemplazarlos por 1 modifica el arreglo a {1, 4, 6, 8}.
Dado que 1 es coprimo con todos los números, la array se puede reducir aún más en los siguientes pasos:
{1, 4, 6, 8} -> {1, 6, 8} -> {1, 8} -> {1}
Por lo tanto, la array se puede reducir al tamaño 1.
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 find the final array
// length by replacing coprime pair with 1
bool hasCoprimePair(vector<int>& arr, int n)
{
// Iterate over all pairs of element
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Check if gcd is 1
if (__gcd(arr[i], arr[j]) == 1) {
return true;
}
}
}
// If no coprime pair
// found return false
return false;
}
// Driver code
int main()
{
int n = 3;
vector<int> arr = { 6, 9, 15 };
// Check if atleast one coprime
// pair exists in the array
if (hasCoprimePair(arr, n)) {
cout << 1 << endl;
}
// If no such pair exists
else {
cout << n << endl;
}
}
Java
// Java Program for the above approach
import java.util.*;
class GFG{
// Recursive function to return
// gcd of a and b
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
// Function to find the final array
// length by replacing coprime pair with 1
static boolean hasCoprimePair(int []arr, int n)
{
// Iterate over all pairs of element
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
// Check if gcd is 1
if ((__gcd(arr[i], arr[j])) == 1)
{
return true;
}
}
}
// If no coprime pair
// found return false
return false;
}
// Driver code
public static void main(String[] args)
{
int n = 3;
int []arr = { 6, 9, 15 };
// Check if atleast one coprime
// pair exists in the array
if (hasCoprimePair(arr, n))
{
System.out.print(1 + "\n");
}
// If no such pair exists
else
{
System.out.print(n + "\n");
}
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach import math # Function to find the final array # length by replacing coprime pair with 1 def hasCoprimePair(arr, n): # Iterate over all pairs of element for i in range(n - 1): for j in range(i + 1, n): # Check if gcd is 1 if (math.gcd(arr[i], arr[j]) == 1): return True # If no coprime pair # found return false return False # Driver code if __name__ == "__main__": n = 3 arr = [ 6, 9, 15 ] # Check if atleast one coprime # pair exists in the array if (hasCoprimePair(arr, n)): print(1) # If no such pair exists else: print(n) # This code is contributed by chitranayal
C#
// C# Program for the above approach
using System;
class GFG{
// Recursive function to return
// gcd of a and b
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
// Function to find the readonly array
// length by replacing coprime pair with 1
static bool hasCoprimePair(int []arr, int n)
{
// Iterate over all pairs of element
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
// Check if gcd is 1
if ((__gcd(arr[i],
arr[j])) == 1)
{
return true;
}
}
}
// If no coprime pair
// found return false
return false;
}
// Driver code
public static void Main(String[] args)
{
int n = 3;
int []arr = { 6, 9, 15 };
// Check if atleast one coprime
// pair exists in the array
if (hasCoprimePair(arr, n))
{
Console.Write(1 + "\n");
}
// If no such pair exists
else
{
Console.Write(n + "\n");
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript Program for the above approach
// Recursive function to return
// gcd of a and b
function __gcd(a , b) {
return b == 0 ? a : __gcd(b, a % b);
}
// Function to find the final array
// length by replacing coprime pair with 1
function hasCoprimePair(arr , n) {
// Iterate over all pairs of element
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
// Check if gcd is 1
if ((__gcd(arr[i], arr[j])) == 1) {
return true;
}
}
}
// If no coprime pair
// found return false
return false;
}
// Driver code
var n = 3;
var arr = [ 6, 9, 15 ];
// Check if atleast one coprime
// pair exists in the array
if (hasCoprimePair(arr, n)) {
document.write(1 + "\n");
}
// If no such pair exists
else {
document.write(n + "\n");
}
// This code contributed by gauravrajput1
</script>
3
Complejidad de Tiempo: O(N 2 * log N)
Espacio Auxiliar: O(1)