Minimice la cantidad de enteros que se agregarán en Array para hacer que cada par adyacente sea coprimo

Dada una array de enteros arr[] de N enteros, la tarea es 
hacer que cada par adyacente en la array sea coprimo, agregando el número mínimo de enteros en la array. Devuelve -1 si no es posible.

Ejemplo: 

Entrada: N = 2, arr = [7, 42]
Salida: 1
Explicación: Después de sumar 11, la array final será [7, 11, 42]. Todos los elementos adyacentes ahora son coprimos

Entrada: N = 4, arr = [2200, 42, 2184, 17]
Salida: 3
Explicación: 43, 2195, 2199 se pueden agregar en la array actual. La array ordenada final será [17, 42, 43, 2184, 2195, 2199, 2200] y todos los pares adyacentes son coprimos.

 

Enfoque: El problema dado se puede resolver haciendo algunas observaciones y teoría básica de números. Se pueden seguir los siguientes pasos:

  • Ordenar la array en orden no decreciente
  • Iterar de izquierda a derecha y verificar cada par adyacente para las siguientes condiciones:
  • Si el par actual es coprimo , entonces no hay necesidad de agregar ningún elemento adicional
  • Si el par actual no es coprimo, itere todos los valores entre los elementos y verifique si el valor actual es coprimo con los pares izquierdo y derecho.
  • De lo contrario, siempre es posible sumar dos valores que son coprimos entre sí y con valores de izquierda y derecha respectivamente.

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

C++

// C++ implementation for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate minimum additions
// required such that no adjacent pairs are
// coprime in their sorted order
int MinimumAdditions(int arr[], int n)
{
    // Sort the given array
    // in non-decreasing order
    sort(arr, arr + n);
 
    // First check if any two adjacent
    // elements are same then
    // the answer will be -1
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1]) {
 
            // Return directly from here
            return -1;
        }
    }
 
    // Variable to store the answer
    int ans = 0;
 
    for (int i = 1; i < n; i++) {
        if (__gcd(arr[i],
                  arr[i - 1])
            == 1) {
            continue;
        }
 
        // Check for a single middle element
        // Maintain a bool value
        bool found = 0;
 
        for (int j = arr[i - 1] + 1;
             j <= arr[i] - 1; j++) {
            if (__gcd(arr[i - 1], j) == 1
                && __gcd(j, arr[i]) == 1) {
                found = 1;
            }
        }
        if (found) {
            ans++;
        }
        else {
            ans += 2;
        }
    }
 
    // return the answer
    return ans;
}
 
// Driver Code
int main()
{
    int N = 4;
    int arr[] = { 2200, 42, 2184, 17 };
    cout << MinimumAdditions(arr, N);
}

Java

// Java implementation for the above approach
import java.io.*;
import java.util.Arrays;
 
class GFG{
 
static int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
 
// Function to calculate minimum additions
// required such that no adjacent pairs are
// coprime in their sorted order
static int MinimumAdditions(int []arr, int n)
{
    // Sort the given array
    // in non-decreasing order
    Arrays.sort(arr);
 
    // First check if any two adjacent
    // elements are same then
    // the answer will be -1
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1]) {
 
            // Return directly from here
            return -1;
        }
    }
 
    // Variable to store the answer
    int ans = 0;
 
    for (int i = 1; i < n; i++) {
        if (gcd(arr[i],
                  arr[i - 1])
            == 1) {
            continue;
        }
 
        // Check for a single middle element
        // Maintain a bool value
        int found = 0;
 
        for (int j = arr[i - 1] + 1;
             j <= arr[i] - 1; j++) {
            if (gcd(arr[i - 1], j) == 1
                && gcd(j, arr[i]) == 1) {
                found = 1;
            }
        }
        if (found!=0) {
            ans++;
        }
        else {
            ans += 2;
        }
    }
 
    // return the answer
    return ans;
}
 
// Driver Code
public static void main(String[] args)
    {
    int N = 4;
    int []arr = { 2200, 42, 2184, 17 };
    System.out.println(MinimumAdditions(arr, N));
}
}
 
// This code is contributed by shivanisinghss2110

Python3

# Python 3 implementation for the above approach
import math
 
# Function to calculate minimum additions
# required such that no adjacent pairs are
# coprime in their sorted order
def MinimumAdditions(arr, n):
 
    # Sort the given array
    # in non-decreasing order
    arr.sort()
 
    # First check if any two adjacent
    # elements are same then
    # the answer will be -1
    for i in range(1,  n):
        if (arr[i] == arr[i - 1]):
 
            # Return directly from here
            return -1
 
    # Variable to store the answer
    ans = 0
 
    for i in range(1, n):
        if (math.gcd(arr[i],
                     arr[i - 1])
                == 1):
            continue
 
        # Check for a single middle element
        # Maintain a bool value
        found = 0
 
        for j in range(arr[i - 1] + 1,
                       arr[i]):
            if (math.gcd(arr[i - 1], j) == 1
                    and math.gcd(j, arr[i]) == 1):
                found = 1
 
        if (found):
            ans += 1
 
        else:
            ans += 2
 
    # return the answer
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    N = 4
    arr = [2200, 42, 2184, 17]
    print(MinimumAdditions(arr, N))
 
    # This code is contributed by ukasp.

C#

// C# implementation for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
static int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}
 
// Function to calculate minimum additions
// required such that no adjacent pairs are
// coprime in their sorted order
static int MinimumAdditions(int []arr, int n)
{
    // Sort the given array
    // in non-decreasing order
    Array.Sort(arr);
 
    // First check if any two adjacent
    // elements are same then
    // the answer will be -1
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1]) {
 
            // Return directly from here
            return -1;
        }
    }
 
    // Variable to store the answer
    int ans = 0;
 
    for (int i = 1; i < n; i++) {
        if (gcd(arr[i],
                  arr[i - 1])
            == 1) {
            continue;
        }
 
        // Check for a single middle element
        // Maintain a bool value
        int found = 0;
 
        for (int j = arr[i - 1] + 1;
             j <= arr[i] - 1; j++) {
            if (gcd(arr[i - 1], j) == 1
                && gcd(j, arr[i]) == 1) {
                found = 1;
            }
        }
        if (found!=0) {
            ans++;
        }
        else {
            ans += 2;
        }
    }
 
    // return the answer
    return ans;
}
 
// Driver Code
public static void Main()
{
    int N = 4;
    int []arr = { 2200, 42, 2184, 17 };
    Console.Write(MinimumAdditions(arr, N));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
       // JavaScript Program to implement
       // the above approach
       // Recursive function to return gcd of a and b
       function __gcd(a, b) {
           // Everything divides 0
           if (a == 0)
               return b;
           if (b == 0)
               return a;
 
           // base case
           if (a == b)
               return a;
 
           // a is greater
           if (a > b)
               return __gcd(a - b, b);
           return __gcd(a, b - a);
       }
 
       // Function to calculate minimum additions
       // required such that no adjacent pairs are
       // coprime in their sorted order
       function MinimumAdditions(arr, n) {
           // Sort the given array
           // in non-decreasing order
           arr.sort(function (a, b) { return a - b; });
 
           // First check if any two adjacent
           // elements are same then
           // the answer will be -1
           for (let i = 1; i < n; i++) {
               if (arr[i] == arr[i - 1]) {
 
                   // Return directly from here
                   return -1;
               }
           }
 
           // Variable to store the answer
           let ans = 0;
 
           for (let i = 1; i < n; i++) {
               if (__gcd(arr[i],
                   arr[i - 1])
                   == 1) {
                   continue;
               }
 
               // Check for a single middle element
               // Maintain a bool value
               let found = 0;
 
               for (let j = arr[i - 1] + 1;
                   j <= arr[i] - 1; j++) {
                   if (__gcd(arr[i - 1], j) == 1
                       && __gcd(j, arr[i]) == 1) {
                       found = 1;
                   }
               }
               if (found) {
                   ans++;
               }
               else {
                   ans += 2;
               }
           }
 
           // return the answer
           return ans;
       }
 
       // Driver Code
 
       let N = 4;
       let arr = [2200, 42, 2184, 17];
       document.write(MinimumAdditions(arr, N));
 
 
    // This code is contributed by Potta Lokesh
 
   </script>
Producción

3

Complejidad de tiempo: O(Nlog(N) + M), donde M es el elemento máximo en la array
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por kartikmodi 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 *