Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar el valor máximo posible de D, de modo que cada elemento de la array se pueda obtener, comenzando desde el valor inicial de K, ya sea cambiando K a K – D o K + D en cada paso.
Ejemplos:
Entrada: arr[ ] = {1, 7, 11}, K = 3
Salida: 2
Explicación:
Considerando que el valor de D es 2, cada elemento de la array se puede obtener mediante las siguientes operaciones:
- arr[0](= 1): Decrementando 2 de K(=3) se obtiene arr[0].
- arr[1](= 7): Incrementando K(=3) por 2 veces D se obtiene arr[1].
- arr[2](= 11): Incrementando K(=3) por 4 veces D se obtiene arr[2].
Por lo tanto, D (=2) satisface las condiciones. Además, es el valor máximo posible de D.
Entrada: arr[ ] = {33, 105, 57}, K = 81
Salida: 24
Enfoque : El problema se puede resolver encontrando el Máximo Común Divisor de la diferencia absoluta entre cada elemento de la array y K. Siga los pasos a continuación para resolver el problema
- Recorra la array arr[] y cambie el valor del elemento actual arr[i] a abs(arr[i] – K) .
- Inicialice una variable, digamos D como arr[0], para almacenar el resultado.
- Iterar en el rango [1, N – 1] usando una variable, digamos i, y en cada iteración, actualizar el valor de D a mcd (D, arr[i]).
- Después de completar los pasos anteriores, imprima el valor de D como respuesta.
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;
// Recursive function tox
// previous gcd of a and b
int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find the maximum value
// of D such that every element in
// the array can be obtained by
// performing K + D or K - D
int findMaxD(int arr[], int N, int K)
{
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Update arr[i]
arr[i] = abs(arr[i] - K);
}
// Stores GCD of the array
int D = arr[0];
// Iterate over the range [1, N]
for (int i = 1; i < N; i++) {
// Update the value of D
D = gcd(D, arr[i]);
}
// Print the value of D
return D;
}
// Driver Code
int main()
{
int arr[] = { 1, 7, 11 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 3;
cout << findMaxD(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Recursive function tox
// previous gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find the maximum value
// of D such that every element in
// the array can be obtained by
// performing K + D or K - D
static int findMaxD(int arr[], int N, int K)
{
// Traverse the array arr[]
for(int i = 0; i < N; i++)
{
// Update arr[i]
arr[i] = Math.abs(arr[i] - K);
}
// Stores GCD of the array
int D = arr[0];
// Iterate over the range [1, N]
for(int i = 1; i < N; i++)
{
// Update the value of D
D = gcd(D, arr[i]);
}
// Print the value of D
return D;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 7, 11 };
int N = arr.length;
int K = 3;
System.out.print(findMaxD(arr, N, K));
}
}
// This code is contributed by rishavmahato348
Python3
# // python program for the above approach # // Recursive function tox # // previous gcd of a and b def gcd(a, b): if (b == 0): return a return gcd(b, a % b) # // Function to find the maximum value # // of D such that every element in # // the array can be obtained by # // performing K + D or K - D def findMaxD(arr, N, K): # // Traverse the array arr[] for i in range(0, N): # // Update arr[i] arr[i] = abs(arr[i] - K) # // Stores GCD of the array D = arr[0] # // Iterate over the range[1, N] for i in range(1, N): # // Update the value of D D = gcd(D, arr[i]) # // Print the value of D return D # // Driver Code arr = [1, 7, 11] N = len(arr) K = 3 print(findMaxD(arr, N, K)) # This code is contributed by amreshkumar3
C#
// C# program for the above approach
using System;
class GFG {
// Recursive function tox
// previous gcd of a and b
static int gcd(int a, int b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find the maximum value
// of D such that every element in
// the array can be obtained by
// performing K + D or K - D
static int findMaxD(int[] arr, int N, int K)
{
// Traverse the array arr[]
for (int i = 0; i < N; i++) {
// Update arr[i]
arr[i] = Math.Abs(arr[i] - K);
}
// Stores GCD of the array
int D = arr[0];
// Iterate over the range [1, N]
for (int i = 1; i < N; i++) {
// Update the value of D
D = gcd(D, arr[i]);
}
// Print the value of D
return D;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 7, 11 };
int N = arr.Length;
int K = 3;
Console.Write(findMaxD(arr, N, K));
}
}
// This code is contributed by subhammahato348.
Javascript
<script>
// Javascript program for the above approach
// Recursive function tox
// previous gcd of a and b
function gcd(a, b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// Function to find the maximum value
// of D such that every element in
// the array can be obtained by
// performing K + D or K - D
function findMaxD(arr, N, K) {
// Traverse the array arr[]
for (let i = 0; i < N; i++) {
// Update arr[i]
arr[i] = Math.abs(arr[i] - K);
}
// Stores GCD of the array
let D = arr[0];
// Iterate over the range [1, N]
for (let i = 1; i < N; i++) {
// Update the value of D
D = gcd(D, arr[i]);
}
// Print the value of D
return D;
}
// Driver Code
let arr = [1, 7, 11];
let N = arr.length;
let K = 3;
document.write(findMaxD(arr, N, K));
// This code is contributed by _saurabh_jaiswal.
</script>
Producción
2
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por hrithikgarg03188 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA