Dada una array de enteros A[ ] de tamaño N , la tarea es encontrar una subsecuencia de tamaño B tal que la diferencia mínima entre dos de ellos sea máxima e imprimir esta diferencia mínima más grande.
Ejemplos:
Entrada: A[ ] = {1, 2, 3, 5}, B = 3
Salida: 2
Explicación:
Las posibles subsecuencias de tamaño 3 son {1, 2, 3}, {1, 2, 5}, {1, 3 , 5} y {2, 3, 5}.
Para {1, 3, 5}, las posibles diferencias son (|1 – 3| = 2), (|3 – 5| = 2) y (|1 – 5| = 4), mínimo (2, 2, 4) = 2
Para las subsecuencias restantes, la diferencia mínima resulta ser 1.
Por lo tanto, el máximo de todas las diferencias mínimas es 2.Entrada: A[ ] = {5, 17, 11}, B = 2
Salida: 12
Explicación:
Las posibles subsecuencias de tamaño 2 son {5, 17}, {17, 11} y {5, 11}.
Para {5, 17}, la posible diferencia es (|5 – 17| = 12), Mínimo = 12
Para {17, 11}, la posible diferencia es (|17 – 11| = 6), Mínimo = 6
Para {5, 11}, la diferencia posible es (|5 – 11| = 6), Mínimo = 6
Máximo (12, 6, 6) = 12
Por lo tanto, el máximo de todas las diferencias mínimas es 12.
Enfoque ingenuo:
el enfoque más simple para resolver este problema es generar todas las subsecuencias posibles de tamaño B y encontrar la diferencia mínima entre todos los pares posibles. Finalmente, encuentre el máximo entre todas las diferencias mínimas.
Complejidad temporal: O(2 N *N 2 )
Espacio auxiliar: O(N)
Enfoque eficiente:
siga los pasos a continuación para optimizar el enfoque anterior utilizando la búsqueda binaria :
- Establezca el espacio de búsqueda de 0 al elemento máximo en la array ( maxm )
- Para cada mid calculado , verifique si es posible obtener una subsecuencia de tamaño B con una diferencia mínima entre cualquier par igual a mid .
- Si es posible, almacene mid en una variable y encuentre una mejor respuesta en la mitad derecha y descarte la mitad izquierda de mid
- De lo contrario, atraviese la mitad izquierda del medio para verificar si existe una subsecuencia con una diferencia mínima de pares más pequeña.
- Finalmente, después de la terminación de la búsqueda binaria, imprima la mitad más alta para la cual se encontró cualquier subsecuencia con diferencia mínima de pares igual a la mitad .
Ilustración:
A[ ] = {1, 2, 3, 4, 5}, B = 3
Espacio de búsqueda: {0, 1, 2, 3, 4, 5}
Los pasos involucrados en la búsqueda binaria son los siguientes:
- start = 0, end = 5, mid = (0 + 5) / 2 = 2
La subsecuencia de tamaño B con diferencia mínima de mid (= 2) es {1, 3, 5}.
Por lo tanto, respuesta = 2- Ahora, atraviesa la mitad derecha.
start = mid +1 = 3, end = 5, mid = (3 + 5) / 2 = 4
La subsecuencia de tamaño B con una diferencia mínima de mid (= 4) no es posible.
Por lo tanto, ans sigue siendo 2.- Ahora, atraviese la mitad izquierda
start = 3, end = mid – 1 = 3, mid = (3 + 3) / 2 = 3
La subsecuencia de tamaño B con una diferencia mínima de mid(= 3) no es posible.
Por lo tanto, ans sigue siendo 2.- De nuevo, atraviesa la mitad izquierda.
start = 3, end = mid – 1 = 2.
Dado que start excede end , la búsqueda binaria termina.- Finalmente, la mayor diferencia mínima posible es 2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check a subsequence can
// be formed with min difference mid
bool can_place(int A[], int n,
int B, int mid)
{
int count = 1;
int last_position = A[0];
// If a subsequence of size B
// with min diff = mid is possible
// return true else false
for (int i = 1; i < n; i++) {
if (A[i] - last_position
>= mid) {
last_position = A[i];
count++;
if (count == B) {
return true;
}
}
}
return false;
}
// Function to find the maximum of
// all minimum difference of pairs
// possible among the subsequence
int find_min_difference(int A[],
int n, int B)
{
// Sort the Array
sort(A, A + n);
// Stores the boundaries
// of the search space
int s = 0;
int e = A[n - 1] - A[0];
// Store the answer
int ans = 0;
// Binary Search
while (s <= e) {
long long int mid = (s + e) / 2;
// If subsequence can be formed
// with min diff mid and size B
if (can_place(A, n, B, mid)) {
ans = mid;
// Right half
s = mid + 1;
}
else {
// Left half
e = mid - 1;
}
}
return ans;
}
// Driver Code
int main()
{
int A[] = { 1, 2, 3, 5 };
int n = sizeof(A) / sizeof(A[0]);
int B = 3;
int min_difference
= find_min_difference(A, n, B);
cout << min_difference;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to check a subsequence can
// be formed with min difference mid
static boolean can_place(int A[], int n,
int B, int mid)
{
int count = 1;
int last_position = A[0];
// If a subsequence of size B
// with min diff = mid is possible
// return true else false
for(int i = 1; i < n; i++)
{
if (A[i] - last_position >= mid)
{
last_position = A[i];
count++;
if (count == B)
{
return true;
}
}
}
return false;
}
// Function to find the maximum of
// all minimum difference of pairs
// possible among the subsequence
static int find_min_difference(int A[],
int n, int B)
{
// Sort the Array
Arrays.sort(A);
// Stores the boundaries
// of the search space
int s = 0;
int e = A[n - 1] - A[0];
// Store the answer
int ans = 0;
// Binary Search
while (s <= e)
{
int mid = (s + e) / 2;
// If subsequence can be formed
// with min diff mid and size B
if (can_place(A, n, B, mid))
{
ans = mid;
// Right half
s = mid + 1;
}
else
{
// Left half
e = mid - 1;
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, 2, 3, 5 };
int n = A.length;
int B = 3;
int min_difference = find_min_difference(A, n, B);
System.out.print(min_difference);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Function to check a subsequence can # be formed with min difference mid def can_place(A, n, B, mid): count = 1 last_position = A[0] # If a subsequence of size B # with min diff = mid is possible # return true else false for i in range(1, n): if (A[i] - last_position >= mid): last_position = A[i] count = count + 1 if (count == B): return bool(True) return bool(False) # Function to find the maximum of # all minimum difference of pairs # possible among the subsequence def find_min_difference(A, n, B): # Sort the Array A.sort() # Stores the boundaries # of the search space s = 0 e = A[n - 1] - A[0] # Store the answer ans = 0 # Binary Search while (s <= e): mid = (int)((s + e) / 2) # If subsequence can be formed # with min diff mid and size B if (can_place(A, n, B, mid)): ans = mid # Right half s = mid + 1 else: # Left half e = mid - 1 return ans # Driver code A = [ 1, 2, 3, 5 ] n = len(A) B = 3 min_difference = find_min_difference(A, n, B) print(min_difference) # This code is contributed by divyeshrabadiya07
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to check a subsequence can
// be formed with min difference mid
static bool can_place(int[] A, int n,
int B, int mid)
{
int count = 1;
int last_position = A[0];
// If a subsequence of size B
// with min diff = mid is possible
// return true else false
for(int i = 1; i < n; i++)
{
if (A[i] - last_position >= mid)
{
last_position = A[i];
count++;
if (count == B)
{
return true;
}
}
}
return false;
}
// Function to find the maximum of
// all minimum difference of pairs
// possible among the subsequence
static int find_min_difference(int[] A,
int n, int B)
{
// Sort the Array
Array.Sort(A);
// Stores the boundaries
// of the search space
int s = 0;
int e = A[n - 1] - A[0];
// Store the answer
int ans = 0;
// Binary Search
while (s <= e)
{
int mid = (s + e) / 2;
// If subsequence can be formed
// with min diff mid and size B
if (can_place(A, n, B, mid))
{
ans = mid;
// Right half
s = mid + 1;
}
else
{
// Left half
e = mid - 1;
}
}
return ans;
}
// Driver Code
public static void Main(string[] args)
{
int[] A = { 1, 2, 3, 5 };
int n = A.Length;
int B = 3;
int min_difference = find_min_difference(A, n, B);
Console.Write(min_difference);
}
}
// This code is contributed by rock_cool
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to check a subsequence can
// be formed with min difference mid
function can_place(A, n, B, mid)
{
let count = 1;
let last_position = A[0];
// If a subsequence of size B
// with min diff = mid is possible
// return true else false
for(let i = 1; i < n; i++)
{
if (A[i] - last_position >= mid)
{
last_position = A[i];
count++;
if (count == B)
{
return true;
}
}
}
return false;
}
// Function to find the maximum of
// all minimum difference of pairs
// possible among the subsequence
function find_min_difference(A, n, B)
{
// Sort the Array
A.sort();
// Stores the boundaries
// of the search space
let s = 0;
let e = A[n - 1] - A[0];
// Store the answer
let ans = 0;
// Binary Search
while (s <= e)
{
let mid = parseInt((s + e) / 2, 10);
// If subsequence can be formed
// with min diff mid and size B
if (can_place(A, n, B, mid))
{
ans = mid;
// Right half
s = mid + 1;
}
else
{
// Left half
e = mid - 1;
}
}
return ans;
}
// Driver code
let A = [ 1, 2, 3, 5 ];
let n = A.length;
let B = 3;
let min_difference = find_min_difference(A, n, B);
document.write(min_difference);
// This code is contributed by divyesh072019
</script>
2
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kritirikhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA