Dados C imanes y una array arr[] que representa N posiciones de índice donde C ≤ N . La tarea es colocar estos imanes en estos índices disponibles de tal manera que la distancia entre los dos imanes más cercanos sea la mayor posible.
Ejemplos:
Entrada: C = 4, arr[] = {1, 2, 5, 8, 10, 18}
Salida: 4
Podemos colocar 4 imanes en las posiciones 1, 5, 10, 18 para que la distancia máxima sea mínima ( dist(1 , 5), dist(5, 10), dist(10, 18) ) = dist(1, 5) = 4.
Y será la distancia máxima posible entre dos imanes más cercanos.
Entrada: C = 3, arr[] = {5, 7, 11, 20, 23}
Salida: 6
Podemos colocar 3 imanes en las posiciones 5, 11, 23 para que la respuesta sea un mínimo de ( dist(5, 11), dist(11, 23) ) = dist(5, 11) = 6.
Enfoque ingenuo: encuentre todas las posiciones posibles de los imanes que sean C (n, c) formas posibles y encuentre una que maximice la distancia entre dos imanes, donde C (n, c) está seleccionando c objetos de n objetos dados.
Enfoque eficiente: Sea mx la máxima distancia posible, por lo tanto todo x mayor que 0 y menor que mx también permitirá colocar imanes pero para todo y mayor que mx, no será posible colocar los imanes. Por lo tanto, podemos usar la búsqueda binaria para encontrar la distancia máxima posible.
Dado que nuestra respuesta siempre estará entre 0 y el índice máximo entre los N índices dados. Por lo tanto, aplique la búsqueda binaria y encuentre el valor medio entre los valores más bajo y más alto, diga ‘medio’, haga una función que verifique si es posible colocar imanes C asumiendo que ‘medio’ es la distancia máxima posible.
La complejidad de tiempo general será O(nlog(n)) ya que la búsqueda binaria tomará O(log(n)) y O(n) para comprobar si es posible colocar todos los imanes C.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible
// to place C magnets assuming mid as
// maximum possible distance
bool isPossible(int arr[], int n, int C, int mid)
{
// Variable magnet will store count of magnets
// that got placed and currPosition will store
// the position of last placed magnet
int magnet = 1, currPosition = arr[0];
for (int i = 1; i < n; i++) {
// If difference between current index and
// last placed index is greater than or equal to mid
// it will allow placing magnet to this index
if (arr[i] - currPosition >= mid) {
magnet++;
// Now this index will become
// last placed index
currPosition = arr[i];
// If count of magnets placed becomes C
if (magnet == C)
return true;
}
}
// If count of placed magnet is
// less than C then return false
return false;
}
// Function for modified binary search
int binarySearch(int n, int C, int arr[])
{
int lo, hi, mid, ans;
// Sort the indices in ascending order
sort(arr, arr + n);
// Minimum possible distance
lo = 0;
// Maximum possible distance
hi = arr[n - 1];
ans = 0;
// Run the loop until lo becomes
// greater than hi
while (lo <= hi) {
mid = (lo + hi) / 2;
// If not possible, decrease value of hi
if (!isPossible(arr, n, C, mid))
hi = mid - 1;
else {
// Update the answer
ans = max(ans, mid);
lo = mid + 1;
}
}
// Return maximum possible distance
return ans;
}
// Driver code
int main()
{
int C = 4;
int arr[] = { 1, 2, 5, 8, 10, 18 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << binarySearch(n, C, arr) << endl;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to check if it is possible
// to place C magnets assuming mid as
// maximum possible distance
static boolean isPossible(int []arr, int n,
int C, int mid)
{
// Variable magnet will store count of magnets
// that got placed and currPosition will store
// the position of last placed magnet
int magnet = 1, currPosition = arr[0];
for (int i = 1; i < n; i++)
{
// If difference between current index and
// last placed index is greater than or equal to mid
// it will allow placing magnet to this index
if (arr[i] - currPosition >= mid)
{
magnet++;
// Now this index will become
// last placed index
currPosition = arr[i];
// If count of magnets placed becomes C
if (magnet == C)
return true;
}
}
// If count of placed magnet is
// less than C then return false
return false;
}
// Function for modified binary search
static int binarySearch(int n, int C, int []arr)
{
int lo, hi, mid, ans;
// Sort the indices in ascending order
Arrays.sort(arr);
// Minimum possible distance
lo = 0;
// Maximum possible distance
hi = arr[n - 1];
ans = 0;
// Run the loop until lo becomes
// greater than hi
while (lo <= hi)
{
mid = (lo + hi) / 2;
// If not possible, decrease value of hi
if (!isPossible(arr, n, C, mid))
hi = mid - 1;
else
{
// Update the answer
ans = Math.max(ans, mid);
lo = mid + 1;
}
}
// Return maximum possible distance
return ans;
}
// Driver code
public static void main(String args[])
{
int C = 4;
int []arr = { 1, 2, 5, 8, 10, 18 };
int n = arr.length;
System.out.println(binarySearch(n, C, arr));
}
}
// This code is contributed by Akanksha Rai
Python3
# Python 3 implementation of the approach # Function to check if it is possible # to place C magnets assuming mid as # maximum possible distance def isPossible(arr, n, C, mid): # Variable magnet will store count of # magnets that got placed and # currPosition will store the position # of last placed magnet magnet = 1 currPosition = arr[0] for i in range(1, n): # If difference between current index # and last placed index is greater than # or equal to mid it will allow placing # magnet to this index if (arr[i] - currPosition >= mid): magnet += 1 # Now this index will become # last placed index currPosition = arr[i] # If count of magnets placed becomes C if (magnet == C): return True # If count of placed magnet is # less than C then return false return False # Function for modified binary search def binarySearch(n, C, arr): # Sort the indices in ascending order arr.sort(reverse = False) # Minimum possible distance lo = 0 # Maximum possible distance hi = arr[n - 1] ans = 0 # Run the loop until lo becomes # greater than hi while (lo <= hi): mid = int((lo + hi) / 2) # If not possible, decrease value of hi if (isPossible(arr, n, C, mid) == False): hi = mid - 1 else: # Update the answer ans = max(ans, mid) lo = mid + 1 # Return maximum possible distance return ans # Driver code if __name__ == '__main__': C = 4 arr = [1, 2, 5, 8, 10, 18] n = len(arr) print(binarySearch(n, C, arr)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to check if it is possible
// to place C magnets assuming mid as
// maximum possible distance
static bool isPossible(int []arr, int n,
int C, int mid)
{
// Variable magnet will store count of magnets
// that got placed and currPosition will store
// the position of last placed magnet
int magnet = 1, currPosition = arr[0];
for (int i = 1; i < n; i++)
{
// If difference between current index and
// last placed index is greater than or equal to mid
// it will allow placing magnet to this index
if (arr[i] - currPosition >= mid)
{
magnet++;
// Now this index will become
// last placed index
currPosition = arr[i];
// If count of magnets placed becomes C
if (magnet == C)
return true;
}
}
// If count of placed magnet is
// less than C then return false
return false;
}
// Function for modified binary search
static int binarySearch(int n, int C, int []arr)
{
int lo, hi, mid, ans;
// Sort the indices in ascending order
Array.Sort(arr);
// Minimum possible distance
lo = 0;
// Maximum possible distance
hi = arr[n - 1];
ans = 0;
// Run the loop until lo becomes
// greater than hi
while (lo <= hi)
{
mid = (lo + hi) / 2;
// If not possible, decrease value of hi
if (!isPossible(arr, n, C, mid))
hi = mid - 1;
else
{
// Update the answer
ans = Math.Max(ans, mid);
lo = mid + 1;
}
}
// Return maximum possible distance
return ans;
}
// Driver code
static void Main()
{
int C = 4;
int []arr = { 1, 2, 5, 8, 10, 18 };
int n = arr.Length;
Console.WriteLine(binarySearch(n, C, arr));
}
}
// This code is contributed by chandan_jnu
PHP
<?php
// PHP implementation of the approach
// Function to check if it is possible
// to place C magnets assuming mid as
// maximum possible distance
function isPossible($arr, $n, $C, $mid)
{
// Variable magnet will store count of magnets
// that got placed and currPosition will store
// the position of last placed magnet
$magnet = 1; $currPosition = $arr[0];
for ($i = 1; $i < $n; $i++)
{
// If difference between current index and
// last placed index is greater than or equal to mid
// it will allow placing magnet to this index
if ($arr[$i] - $currPosition >= $mid)
{
$magnet++;
// Now this index will become
// last placed index
$currPosition = $arr[$i];
// If count of magnets placed becomes C
if ($magnet == $C)
return true;
}
}
// If count of placed magnet is
// less than C then return false
return false;
}
// Function for modified binary search
function binarySearch($n, $C, $arr)
{
// Sort the indices in ascending order
sort($arr, 0);
// Minimum possible distance
$lo = 0;
// Maximum possible distance
$hi = $arr[$n - 1];
$ans = 0;
// Run the loop until lo becomes
// greater than hi
while ($lo <= $hi)
{
$mid = ($lo + $hi) / 2;
// If not possible, decrease value of hi
if (!isPossible($arr, $n, $C, $mid))
$hi = $mid - 1;
else
{
// Update the answer
$ans = max($ans, $mid);
$lo = $mid + 1;
}
}
// Return maximum possible distance
return $ans;
}
// Driver code
$C = 4;
$arr = array(1, 2, 5, 8, 10, 18);
$n = sizeof($arr);
echo binarySearch($n, $C, $arr) . "\n";
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to check if it is possible
// to place C magnets assuming mid as
// maximum possible distance
function isPossible(arr, n, C, mid)
{
// Variable magnet will store count of magnets
// that got placed and currPosition will store
// the position of last placed magnet
let magnet = 1; currPosition = arr[0];
for (let i = 1; i < n; i++)
{
// If difference between current index and
// last placed index is greater than or equal to mid
// it will allow placing magnet to this index
if (arr[i] - currPosition >= mid)
{
magnet++;
// Now this index will become
// last placed index
currPosition = arr[i];
// If count of magnets placed becomes C
if (magnet == C)
return true;
}
}
// If count of placed magnet is
// less than C then return false
return false;
}
// Function for modified binary search
function binarySearch(n, C, arr)
{
// Sort the indices in ascending order
arr.sort((a, b) => a - b);
// Minimum possible distance
let lo = 0;
// Maximum possible distance
let hi = arr[n - 1];
let ans = 0;
// Run the loop until lo becomes
// greater than hi
while (lo <= hi)
{
mid = Math.floor((lo + hi) / 2);
// If not possible, decrease value of hi
if (!isPossible(arr, n, C, mid))
hi = mid - 1;
else
{
// Update the answer
ans = Math.max(ans, mid);
lo = mid + 1;
}
}
// Return maximum possible distance
return ans;
}
// Driver code
let C = 4;
let arr = new Array(1, 2, 5, 8, 10, 18);
let n = arr.length;
document.write(binarySearch(n, C, arr) + "<br>");
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
4
Complejidad de tiempo: O(n * log(n))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Vivek.Pandit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA