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 coprimosEntrada: 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