Dada una array ordenada arr[] que consta de N enteros, que representan puntos en una línea y un número entero K , la tarea es encontrar cualquier punto P entre el primero y el último punto tal que la suma de las distancias de todos los puntos dados desde P sea igual a k _ Si no existe tal punto, imprima “-1” .
Ejemplos:
Entrada: arr[] = {1, 3, 6, 7, 11}, K = 18
Salida: 8
Explicación:
Considere el valor de P como 8. Por lo tanto, la suma de la distancia de P(= 8) desde todos los puntos es (8 – 1) + (8 – 3) + (8 – 6) + (8 – 7) + (11 – 8) = 18( =K) que es igual al valor dado K y el punto 8 se encuentra entre el primero (= 1) y el último (= 11) punto.Entrada: arr[] = {-10, -2, 1, 2}, K= 29
Salida: -9
Planteamiento: El problema dado se puede resolver con base en la observación de que la suma de las distancias será mínima en la mediana del arreglo y la distancia aumenta cuando se mueve desde la mediana hacia cualquiera de los extremos. Entonces, la idea es realizar una búsqueda binaria en ambas mitades de la array y verificar si algún punto tiene una distancia igual a K . Siga los pasos a continuación para resolver el problema:
- Declare una función que calcule la suma de las distancias de todos los puntos desde un punto dado.
- Realice una búsqueda binaria en la mitad derecha de la array como:
- Si el valor de N es impar, actualice el valor de left como arr[N / 2] . De lo contrario, actualice el valor de left como arr[N / 2 – 1] + 1 .
- Si el valor de N es par, actualice el valor de right como arr[N – 1] .
- Encuentre la suma de las distancias, digamos temperatura desde la mitad = (izquierda + derecha) / 2 y verifique si el valor de la temperatura es igual a K o no. SI se encuentra que es verdadero , imprima el valor de mid como resultado.
- Si el valor de K < temp , actualice el valor de right como mid – 1 . De lo contrario, actualice el valor de left como mid + 1 .
- Realice una búsqueda binaria en la mitad izquierda de la array:
- Establezca el valor de left = arr[0] y right = arr[N / 2] – 1 .
- Encuentre la suma de las distancias, por ejemplo, la temperatura desde la mitad = (izquierda + derecha) / 2 y verifique si la temperatura es igual a K o no. Si se encuentra que es verdadero , imprima el valor de mid como resultado.
- Si el valor de K > temp , actualice el valor de right = mid – 1 . De lo contrario, actualice el valor de left = mid + 1 .
- Si no se encuentra ningún valor en la mitad izquierda y derecha, imprima «-1» 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 the sum of distances
// of all points from a given point
int findSum(int* arr, int N, int pt)
{
// Stores sum of distances
int sum = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
sum += abs(arr[i] - pt);
}
// Return the sum
return sum;
}
// Function to find such a point having
// sum of distances of all other points
// from this point equal to K
void findPoint(int* arr, int N, int K)
{
// If N is odd keep left as arr[n / 2]
// else keep left as arr[n / 2 - 1] + 1;
int left;
if (N % 2) {
left = arr[N / 2];
}
else {
left = arr[N / 2 - 1] + 1;
}
// Keep right as arr[N - 1]
int right = arr[N - 1];
// Perform binary search in the
// right half
while (left <= right) {
// Calculate the mid index
// of the range
int mid = (left + right) / 2;
int temp = findSum(arr, N, mid);
// If temp is equal to K
if (temp == K) {
// Print the value of mid
cout << mid << endl;
return;
}
// If the value of K < temp
else if (K < temp) {
// Update right to mid - 1
right = mid - 1;
}
// If the value of K > temp
else {
// Update left to mid + 1
left = mid + 1;
}
}
// Update the value of left
left = arr[0];
// Update the value of right
right = arr[N / 2] - 1;
// Perform binary search on the
// left half
while (left <= right) {
// Calculate the mid index
// of the range
int mid = (left + right) / 2;
int temp = findSum(arr, N, mid);
// If temp is equal to K
if (temp == K) {
// Print mid
cout << mid << endl;
return;
}
// if K > temp
else if (K > temp) {
// Update right to mid - 1
right = mid - 1;
}
// If K < temp
else {
// Update left to mid + 1
left = mid + 1;
}
}
// If no such point found
cout << "-1" << endl;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 6, 7, 11 };
int K = 18;
int N = sizeof(arr) / sizeof(arr[0]);
findPoint(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
class GFG{
// Function to find the sum of distances
// of all points from a given point
public static int findSum(int arr[], int N,
int pt)
{
// Stores sum of distances
int sum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
sum += Math.abs(arr[i] - pt);
}
// Return the sum
return sum;
}
// Function to find such a point having
// sum of distances of all other points
// from this point equal to K
public static void findPoint(int arr[], int N, int K)
{
// If N is odd keep left as arr[n / 2]
// else keep left as arr[n / 2 - 1] + 1;
int left;
if (N % 2 != 0)
{
left = arr[N / 2];
}
else
{
left = arr[N / 2 - 1] + 1;
}
// Keep right as arr[N - 1]
int right = arr[N - 1];
// Perform binary search in the
// right half
while (left <= right)
{
// Calculate the mid index
// of the range
int mid = (left + right) / 2;
int temp = findSum(arr, N, mid);
// If temp is equal to K
if (temp == K)
{
// Print the value of mid
System.out.println(mid);
return;
}
// If the value of K < temp
else if (K < temp)
{
// Update right to mid - 1
right = mid - 1;
}
// If the value of K > temp
else
{
// Update left to mid + 1
left = mid + 1;
}
}
// Update the value of left
left = arr[0];
// Update the value of right
right = arr[N / 2] - 1;
// Perform binary search on the
// left half
while (left <= right)
{
// Calculate the mid index
// of the range
int mid = (left + right) / 2;
int temp = findSum(arr, N, mid);
// If temp is equal to K
if (temp == K)
{
// Print mid
System.out.println(mid);
return;
}
// if K > temp
else if (K > temp)
{
// Update right to mid - 1
right = mid - 1;
}
// If K < temp
else
{
// Update left to mid + 1
left = mid + 1;
}
}
// If no such point found
System.out.println( "-1" );
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 3, 6, 7, 11 };
int K = 18;
int N = arr.length;
findPoint(arr, N, K);
}
}
// This code is contributed by SoumikMondal
Python3
# python 3 program for the above approach
# Function to find the sum of distances
# of all points from a given point
def findSum(arr, N, pt):
# Stores sum of distances
sum = 0
# Traverse the array
for i in range(N):
sum += abs(arr[i] - pt)
# Return the sum
return sum
# Function to find such a point having
# sum of distances of all other points
# from this point equal to K
def findPoint(arr, N, K):
# If N is odd keep left as arr[n / 2]
# else keep left as arr[n / 2 - 1] + 1;
left = 0
if (N % 2):
left = arr[N // 2]
else:
left = arr[N // 2 - 1] + 1
# Keep right as arr[N - 1]
right = arr[N - 1]
# Perform binary search in the
# right half
while (left <= right):
# Calculate the mid index
# of the range
mid = (left + right) // 2
temp = findSum(arr, N, mid)
# If temp is equal to K
if (temp == K):
# Print the value of mid
print(mid)
return
# If the value of K < temp
elif (K < temp):
# Update right to mid - 1
right = mid - 1
# If the value of K > temp
else:
# Update left to mid + 1
left = mid + 1
# Update the value of left
left = arr[0]
# Update the value of right
right = arr[N // 2] - 1
# Perform binary search on the
# left half
while (left <= right):
# Calculate the mid index
# of the range
mid = (left + right) // 2
temp = findSum(arr, N, mid)
# If temp is equal to K
if (temp == K):
# Print mid
print(mid)
return
# if K > temp
elif(K > temp):
# Update right to mid - 1
right = mid - 1
# If K < temp
else:
# Update left to mid + 1
left = mid + 1
# If no such point found
print("-1")
# Driver Code
if __name__ == '__main__':
arr = [1, 3, 6, 7, 11]
K = 18
N = len(arr)
findPoint(arr, N, K)
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the sum of distances
// of all points from a given point
public static int findSum(int[] arr, int N, int pt)
{
// Stores sum of distances
int sum = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
sum += Math.Abs(arr[i] - pt);
}
// Return the sum
return sum;
}
// Function to find such a point having
// sum of distances of all other points
// from this point equal to K
public static void findPoint(int[] arr, int N, int K)
{
// If N is odd keep left as arr[n / 2]
// else keep left as arr[n / 2 - 1] + 1;
int left;
if (N % 2 != 0)
{
left = arr[N / 2];
}
else
{
left = arr[N / 2 - 1] + 1;
}
// Keep right as arr[N - 1]
int right = arr[N - 1];
// Perform binary search in the
// right half
while (left <= right)
{
// Calculate the mid index
// of the range
int mid = (left + right) / 2;
int temp = findSum(arr, N, mid);
// If temp is equal to K
if (temp == K)
{
// Print the value of mid
Console.WriteLine(mid);
return;
}
// If the value of K < temp
else if (K < temp)
{
// Update right to mid - 1
right = mid - 1;
}
// If the value of K > temp
else
{
// Update left to mid + 1
left = mid + 1;
}
}
// Update the value of left
left = arr[0];
// Update the value of right
right = arr[N / 2] - 1;
// Perform binary search on the
// left half
while (left <= right)
{
// Calculate the mid index
// of the range
int mid = (left + right) / 2;
int temp = findSum(arr, N, mid);
// If temp is equal to K
if (temp == K)
{
// Print mid
Console.WriteLine(mid);
return;
}
// if K > temp
else if (K > temp)
{
// Update right to mid - 1
right = mid - 1;
}
// If K < temp
else
{
// Update left to mid + 1
left = mid + 1;
}
}
// If no such point found
Console.WriteLine("-1");
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 1, 3, 6, 7, 11 };
int K = 18;
int N = arr.Length;
findPoint(arr, N, K);
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program for the above approach
// Function to find the sum of distances
// of all points from a given point
function findSum(arr, N, pt)
{
// Stores sum of distances
var sum = 0;
var i;
// Traverse the array
for(i = 0; i < N; i++)
{
sum += Math.abs(arr[i] - pt);
}
// Return the sum
return sum;
}
// Function to find such a point having
// sum of distances of all other points
// from this point equal to K
function findPoint(arr, N, K)
{
// If N is odd keep left as arr[n / 2]
// else keep left as arr[n / 2 - 1] + 1;
var left;
if (N % 2 == 1)
{
left = arr[parseInt(N / 2)];
}
else
{
left = arr[parseInt(N / 2) - 1] + 1;
}
// Keep right as arr[N - 1]
var right = arr[N - 1];
// Perform binary search in the
// right half
while (left <= right)
{
// Calculate the mid index
// of the range
var mid = parseInt((left + right) / 2);
var temp = findSum(arr, N, mid);
// If temp is equal to K
if (temp == K)
{
// Print the value of mid
document.write(mid);
return;
}
// If the value of K < temp
else if (K < temp)
{
// Update right to mid - 1
right = mid - 1;
}
// If the value of K > temp
else
{
// Update left to mid + 1
left = mid + 1;
}
}
// Update the value of left
left = arr[0];
// Update the value of right
right = arr[parseInt(N / 2)] - 1;
// Perform binary search on the
// left half
while (left <= right)
{
// Calculate the mid index
// of the range
var mid = parseInt((left + right) / 2);
var temp = findSum(arr, N, mid);
// If temp is equal to K
if (temp == K)
{
// Print mid
document.write(mid);
return;
}
// If K > temp
else if (K > temp)
{
// Update right to mid - 1
right = mid - 1;
}
// If K < temp
else
{
// Update left to mid + 1
left = mid + 1;
}
}
// If no such point found
document.write("-1");
}
// Driver Code
var arr = [ 1, 3, 6, 7, 11 ];
var K = 18;
var N = arr.length;
findPoint(arr, N, K);
// This code is contributed by bgangwar59
</script>
Producción:
8
Complejidad de tiempo: O(N * log 2 (M – m)) donde M es el valor máximo y m es el valor mínimo de la array.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA