Dada una array de rangos arr[] de longitud N y un número D , la tarea es encontrar la cantidad mínima por la cual el número D debe cambiarse de modo que D se encuentre en cada rango de la array dada. Aquí, un rango consta de dos enteros [inicio, final] y se dice que D está dentro del rango, si inicio ≤ D ≤ final .
Ejemplos:
Entrada: N = 3, D = 3
arr[] = {{0, 7}, {2, 14}, {4, 6}}
Salida: 1
Explicación:
aquí, si incrementamos D en 1, estará dentro de cada rango que es inicio ≤ D ≤ final.Entrada: N = 2, D = 2
arr[] = {{1, 2}, {3, 2}}
Salida: 0
Explicación:
Aquí D = 2 que ya está dentro de cada rango que es inicio ≤ D ≤ final.
Enfoque :
- Iterar sobre la array de rangos y encontrar el valor máximo de start[i] y el valor mínimo de end[i] donde max_start y min_end finales mostrarán el rango común de la array de rangos dada.
- Verifique que D ya esté dentro de max_start y min_end calculado.
- Si D ya está dentro del rango, entonces la diferencia mínima es 0.
- De lo contrario, encuentre el valor más cercano a D de max_start y min_end que es
min(abs(D - max_start), abs(D - min_end))
A continuación se muestra el código del enfoque anterior:
C++
// C++ implementation find the minimum
// difference in the number D such that
// D is inside of every range
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// difference in the number D such that
// D is inside of every range
void findMinimumOperation(int n, int d,
int arrays[3][2]){
int cnt = 0;
int first = INT_MIN, end = INT_MAX;
// Loop to find the common range out
// of the given array of ranges.
while (n--) {
// Storing the start and end index
int arr[2] = { arrays[cnt][0],
arrays[cnt][1] };
// Sorting the range
sort(arr, arr + 2);
// Finding the maximum starting
// value of common segment
first = max(first, arr[0]);
// Finding the minimum ending
// value of common segment
end = min(end, arr[1]);
cnt++;
}
// If there is no common segment
if (first > end)
cout << "-1";
else {
// If the given number is between
// the computed common range.
if (d >= first && d <= end) {
cout << "0";
}
// Finding the minimum distance
else
cout << min(abs(first - d),
abs(d - end));
}
}
// Driver Code
int main()
{
int n = 3, d = 3;
// Given array of ranges
int arrays[3][2] = {
{ 0, 7 },
{ 2, 14 },
{ 4, 6 }
};
findMinimumOperation(n, d, arrays);
}
Java
// Java implementation find the minimum
// difference in the number D such that
// D is inside of every range
import java.util.*;
class GFG
{
// Function to find the minimum
// difference in the number D such that
// D is inside of every range
static void findMinimumOperation(int n, int d,
int arrays[][]){
int cnt = 0;
int first = Integer.MIN_VALUE, end = Integer.MAX_VALUE;
// Loop to find the common range out
// of the given array of ranges.
while (n > 0) {
// Storing the start and end index
int arr[] = { arrays[cnt][0],
arrays[cnt][1] };
// Sorting the range
Arrays.sort(arr);
// Finding the maximum starting
// value of common segment
first = Math.max(first, arr[0]);
// Finding the minimum ending
// value of common segment
end = Math.min(end, arr[1]);
cnt++;
n--;
}
// If there is no common segment
if (first > end)
System.out.print("-1");
else {
// If the given number is between
// the computed common range.
if (d >= first && d <= end) {
System.out.print("0");
}
// Finding the minimum distance
else
System.out.print(Math.min(Math.abs(first - d),
Math.abs(d - end)));
}
}
// Driver Code
public static void main (String []args)
{
int n = 3, d = 3;
// Given array of ranges
int arrays[][] = {
{ 0, 7 },
{ 2, 14 },
{ 4, 6 }
};
findMinimumOperation(n, d, arrays);
}
}
// This code is contributed by chitranayal
Python3
# Python3 implementation find the minimum
# difference in the number D such that
# D is inside of every range
# Function to find the minimum
# difference in the number D such that
# D is inside of every range
def findMinimumOperation(n, d,arrays):
cnt = 0
first = -10**9
end = 10**9
# Loop to find the common range out
# of the given array of ranges.
while (n):
# Storing the start and end index
arr = [arrays[cnt][0],arrays[cnt][1]]
# Sorting the range
arr = sorted(arr)
# Finding the maximum starting
# value of common segment
first = max(first, arr[0])
# Finding the minimum ending
# value of common segment
end = min(end, arr[1])
cnt += 1
n -= 1
# If there is no common segment
if (first > end):
print("-1",end="")
else:
# If the given number is between
# the computed common range.
if (d >= first and d <= end):
print("0",end="")
# Finding the minimum distance
else:
print(min(abs(first - d),abs(d - end)),end="")
# Driver Code
if __name__ == '__main__':
n = 3
d = 3
# Given array of ranges
arrays=[[0, 7],
[2, 14],
[4, 6] ]
findMinimumOperation(n, d, arrays)
# This code is contributed by mohit kumar 29
C#
// C# implementation find the minimum
// difference in the number D such that
// D is inside of every range
using System;
class GFG
{
// Function to find the minimum
// difference in the number D such that
// D is inside of every range
static void findMinimumOperation(int n, int d,
int [,]arrays){
int cnt = 0;
int first = int.MinValue, end = int.MaxValue;
// Loop to find the common range out
// of the given array of ranges.
while (n > 0) {
// Storing the start and end index
int []arr = { arrays[cnt, 0],
arrays[cnt, 1] };
// Sorting the range
Array.Sort(arr);
// Finding the maximum starting
// value of common segment
first = Math.Max(first, arr[0]);
// Finding the minimum ending
// value of common segment
end = Math.Min(end, arr[1]);
cnt++;
n--;
}
// If there is no common segment
if (first > end)
Console.Write("-1");
else {
// If the given number is between
// the computed common range.
if (d >= first && d <= end) {
Console.Write("0");
}
// Finding the minimum distance
else
Console.Write(Math.Min(Math.Abs(first - d),
Math.Abs(d - end)));
}
}
// Driver Code
public static void Main(String []args)
{
int n = 3, d = 3;
// Given array of ranges
int [,]arrays = {
{ 0, 7 },
{ 2, 14 },
{ 4, 6 }
};
findMinimumOperation(n, d, arrays);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript implementation find the minimum
// difference in the number D such that
// D is inside of every range
// Function to find the minimum
// difference in the number D such that
// D is inside of every range
function findMinimumOperation(n, d, arrays)
{
var cnt = 0;
var first = Number.MIN_VALUE,
end = Number.MAX_VALUE;
// Loop to find the common range out
// of the given array of ranges.
while (n > 0)
{
// Storing the start and end index
var arr = [arrays[cnt][0], arrays[cnt][1]];
// Sorting the range
arr.sort((a, b) => a - b);
// Finding the maximum starting
// value of common segment
first = Math.max(first, arr[0]);
// Finding the minimum ending
// value of common segment
end = Math.min(end, arr[1]);
cnt++;
n--;
}
// If there is no common segment
if (first > end)
document.write("-1");
else
{
// If the given number is between
// the computed common range.
if (d >= first && d <= end)
{
document.write("0");
}
// Finding the minimum distance
else
document.write(Math.min(
Math.abs(first - d),
Math.abs(d - end)));
}
}
// Driver Code
var n = 3, d = 3;
// Given array of ranges
var arrays = [ [ 0, 7 ],
[ 2, 14 ],
[ 4, 6 ] ];
findMinimumOperation(n, d, arrays);
// This code is contributed by Rajput-Ji
</script>
Producción:
1
Publicación traducida automáticamente
Artículo escrito por dangenmaster2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA