Dada una array arr[] que consiste en N enteros positivos y un entero positivo K , la tarea es encontrar el máximo entero posible X , tal que la diferencia absoluta entre cualquier elemento de la array y X sea como máximo K . Si no existe tal valor de X , imprima «-1» .
Ejemplos:
Entrada: arr[] = {6, 4, 8, 5}, K = 2
Salida: 6
Explicación: Considerando que X es 6 , la diferencia absoluta entre cada elemento del arreglo y X(= 6) es como máximo K (= 2 ), como se ilustra a continuación:
- Diferencia absoluta entre arr[0](= 6) y X(= 6) = |6 – 6| = 0.
- Diferencia absoluta entre arr[1](= 4) y X(= 6) = |4 – 6| = 2
- Diferencia absoluta entre arr[2](= 8) y X(= 6) = |8 – 6| = 2
- Diferencia absoluta entre arr[3](= 5) y X(= 6) = |5 – 6| = 1.
Entrada: arr[] = {1, 2, 5}, K = 2
Salida: 3
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Considerando que los elementos de la array son arr[i] , el valor de |arr[i] – X| debe ser como máximo K .
- Si arr[i] > X , entonces X ≤ (arr[i] – K) . De lo contrario, X ≤ (arr[i] + K) .
- De las dos ecuaciones anteriores, el valor máximo de X debe ser la suma del valor mínimo de arr[i] y K .
Siga los pasos a continuación para resolver el problema:
- Encuentre el elemento más pequeño de la array dada arr[] en una variable, digamos S .
- Considere el valor máximo de X como (S + K) .
- Recorra la array dada arr[] y si el valor de la diferencia absoluta de arr[i] y X es K , entonces actualice X a -1 y salga del bucle . De lo contrario, continúa con la iteración .
- Después de completar los pasos anteriores, imprima el valor de X como resultado.
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 find maximum value
// of X such that |A[i] - X| ≤ K
int maximumNumber(int arr[], int N,
int K)
{
// Stores the smallest array element
int minimum = *min_element(arr,
arr + N);
// Store the possible value of X
int ans = minimum + K;
// Traverse the array A[]
for (int i = 0; i < N; i++) {
// If required criteria is not satisfied
if (abs(arr[i] - ans) > K) {
// Update ans
ans = -1;
break;
}
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 5 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
maximumNumber(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find maximum value
// of X such that |A[i] - X| ≤ K
static void maximumNumber(int arr[], int N,
int K)
{
// Stores the smallest array element
int minimum = Arrays.stream(arr).min().getAsInt();
// Store the possible value of X
int ans = minimum + K;
// Traverse the array A[]
for(int i = 0; i < N; i++)
{
// If required criteria is not satisfied
if (Math.abs(arr[i] - ans) > K)
{
// Update ans
ans = -1;
break;
}
}
// Print the result
System.out.print(ans);
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 2, 5 };
int K = 2;
int N = arr.length;
maximumNumber(arr, N, K);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find maximum value # of X such that |A[i] - X| ≤ K def maximumNumber(arr, N, K): # Stores the smallest array element minimum = min(arr) # Store the possible value of X ans = minimum + K # Traverse the array A[] for i in range(N): # If required criteria is not satisfied if (abs(arr[i] - ans) > K): # Update ans ans = -1 break # Print the result print(ans) # Driver Code if __name__ == '__main__': arr = [1, 2, 5] K = 2 N = len(arr) maximumNumber(arr, N, K) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find maximum value
// of X such that |A[i] - X| ≤ K
static void maximumNumber(int []arr, int N,
int K)
{
// Stores the smallest array element
int mn = 100000000;
for(int i = 0; i < N; i++)
{
if (arr[i] < mn)
mn = arr[i];
}
// Store the possible value of X
int ans = mn + K;
// Traverse the array A[]
for(int i = 0; i < N; i++)
{
// If required criteria is not satisfied
if (Math.Abs(arr[i] - ans) > K)
{
// Update ans
ans = -1;
break;
}
}
// Print the result
Console.Write(ans);
}
// Driver Code
public static void Main()
{
int []arr = { 1, 2, 5 };
int K = 2;
int N = arr.Length;
maximumNumber(arr, N, K);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// Javascript program for
// the above approach
// Function to find maximum value
// of X such that |A[i] - X| ≤ K
function maximumNumber(arr, N, K)
{
// Stores the smallest
// array element
let minimum = Math.min(...arr)
// Store the possible value of X
let ans = minimum + K;
// Traverse the array A[]
for (let i = 0; i < N; i++) {
// If required criteria is
// not satisfied
if (Math.abs(arr[i] - ans) > K)
{
// Update ans
ans = -1;
break;
}
}
// Print the result
document.write(ans)
}
// Driver Code
let arr = [1, 2, 5]
let K = 2
let N = arr.length
maximumNumber(arr, N, K);
// This code is contributed by Hritik
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitmanathiya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA