Dada una array arr[] que consiste en N enteros y dos enteros positivos L y R , la tarea es encontrar el número coprimo más lejano en el rango [L, R] para cada elemento de la array.
Ejemplos:
Entrada: arr[] = {5, 150, 120}, L = 2, R = 250
Salida: 249 7 247
Explicación:
El número coprimo con arr[0] y más alejado es 249.
El número que es coprimo con arr[1] y el más alejado es 7.
El número que es coprimo con arr[2] y el más alejado es 247.Entrada: arr[] = {60, 246, 75, 103, 155, 110}, L = 2, R = 250
Salida: 60 246 75 103 155 110
Enfoque: el problema dado se puede resolver iterando sobre el rango dado [L, R] para cada elemento de la array y encontrar el elemento más alejado que tenga GCD 1 con el elemento de la array. Siga los pasos a continuación para resolver el problema:
- Recorra la array dada arr[] y realice los siguientes pasos:
- Inicialice dos variables, digamos d como 0 y coPrime como -1 , para almacenar la distancia más lejana y el número coprimo con arr[i] respectivamente.
- Iterar sobre el rango dado [L, R] y realizar los siguientes pasos:
- Actualice el valor de d como la diferencia absoluta de arr[i] y j .
- Si el máximo común divisor de arr[i] y j es 1 y d es menor que abs(arr[i] – j) , actualice el valor de coPrime como j .
- Actualice el valor de arr[i] como coPrime .
- Después de completar los pasos anteriores, imprima la array arr[] como la array resultante.
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 calculate GCD
// of the integers a and b
int gcd(int a, int b)
{
// Base Case
if (a == 0)
return b;
// Recursively find the GCD
return gcd(b % a, a);
}
// Function to find the farthest
// co-prime number over the range
// [L, R] for each array element
void update(int arr[], int n)
{
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
// Stores the distance
// between j and arr[i]
int d = 0;
// Stores the integer coprime
// which is coprime is arr[i]
int coPrime = -1;
// Traverse the range [2, 250]
for (int j = 2; j <= 250; j++) {
// If gcd of arr[i] and j is 1
if (gcd(arr[i], j) == 1
&& d < abs(arr[i] - j)) {
// Update the value of d
d = abs(arr[i] - j);
// Update the value
// of coPrime
coPrime = j;
}
}
// Update the value of arr[i]
arr[i] = coPrime;
}
// Print the array arr[]
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Driver Code
int main()
{
int arr[] = { 60, 246, 75, 103, 155, 110 };
int N = sizeof(arr) / sizeof(arr[0]);
update(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to calculate GCD
// of the integers a and b
static int gcd(int a, int b)
{
// Base Case
if (a == 0)
return b;
// Recursively find the GCD
return gcd(b % a, a);
}
// Function to find the farthest
// co-prime number over the range
// [L, R] for each array element
static void update(int arr[], int n)
{
// Traverse the array arr[]
for(int i = 0; i < n; i++)
{
// Stores the distance
// between j and arr[i]
int d = 0;
// Stores the integer coprime
// which is coprime is arr[i]
int coPrime = -1;
// Traverse the range [2, 250]
for(int j = 2; j <= 250; j++)
{
// If gcd of arr[i] and j is 1
if (gcd(arr[i], j) == 1 &&
d < Math.abs(arr[i] - j))
{
// Update the value of d
d = Math.abs(arr[i] - j);
// Update the value
// of coPrime
coPrime = j;
}
}
// Update the value of arr[i]
arr[i] = coPrime;
}
// Print the array arr[]
for(int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 60, 246, 75, 103, 155, 110 };
int N = arr.length;
update(arr, N);
}
}
// This code is contributed by Kingash
Python3
# python 3 program for the above approach from math import gcd # Function to find the farthest # co-prime number over the range # [L, R] for each array element def update(arr, n): # Traverse the array arr[] for i in range(n): # Stores the distance # between j and arr[i] d = 0 # Stores the integer coprime # which is coprime is arr[i] coPrime = -1 # Traverse the range [2, 250] for j in range(2, 251, 1): # If gcd of arr[i] and j is 1 if (gcd(arr[i], j) == 1 and d < abs(arr[i] - j)): # Update the value of d d = abs(arr[i] - j) # Update the value # of coPrime coPrime = j # Update the value of arr[i] arr[i] = coPrime # Print the array arr[] for i in range(n): print(arr[i],end =" ") # Driver Code if __name__ == '__main__': arr = [60, 246, 75, 103, 155, 110] N = len(arr) update(arr, N) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG {
// Function to calculate GCD
// of the integers a and b
static int gcd(int a, int b)
{
// Base Case
if (a == 0)
return b;
// Recursively find the GCD
return gcd(b % a, a);
}
// Function to find the farthest
// co-prime number over the range
// [L, R] for each array element
static void update(int[] arr, int n)
{
// Traverse the array arr[]
for (int i = 0; i < n; i++) {
// Stores the distance
// between j and arr[i]
int d = 0;
// Stores the integer coprime
// which is coprime is arr[i]
int coPrime = -1;
// Traverse the range [2, 250]
for (int j = 2; j <= 250; j++) {
// If gcd of arr[i] and j is 1
if (gcd(arr[i], j) == 1
&& d < Math.Abs(arr[i] - j)) {
// Update the value of d
d = Math.Abs(arr[i] - j);
// Update the value
// of coPrime
coPrime = j;
}
}
// Update the value of arr[i]
arr[i] = coPrime;
}
// Print the array arr[]
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 60, 246, 75, 103, 155, 110 };
int N = arr.Length;
update(arr, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to calculate GCD
// of the integers a and b
function gcd(a, b)
{
// Base Case
if (a == 0)
return b;
// Recursively find the GCD
return gcd(b % a, a);
}
// Function to find the farthest
// co-prime number over the range
// [L, R] for each array element
function update(arr, n)
{
// Traverse the array arr[]
for(let i = 0; i < n; i++)
{
// Stores the distance
// between j and arr[i]
let d = 0;
// Stores the integer coprime
// which is coprime is arr[i]
let coPrime = -1;
// Traverse the range [2, 250]
for(let j = 2; j <= 250; j++)
{
// If gcd of arr[i] and j is 1
if (gcd(arr[i], j) == 1 &&
d < Math.abs(arr[i] - j))
{
// Update the value of d
d = Math.abs(arr[i] - j);
// Update the value
// of coPrime
coPrime = j;
}
}
// Update the value of arr[i]
arr[i] = coPrime;
}
// Print the array arr[]
for(let i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Driver code
let arr = [ 60, 246, 75, 103, 155, 110 ];
let N = arr.length;
update(arr, N)
</script>
Producción:
247 5 248 250 2 249
Complejidad de Tiempo: O((R – L) * N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kfardeen7890 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA