Valor mínimo posible de D que, cuando se suma o se resta de K, obtiene repetidamente todos los elementos de la array

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *