Given a sorted array arr[] consisting of N integers, representing points on a line and an integer K, the task is to find any point P between the first and last point such that the sum of distances of all given points from P is equal to K. If no such point exists, then print “-1”.
Examples:
Input: arr[] = {1, 3, 6, 7, 11}, K = 18
Output: 8
Explanation:
Consider the value of P as 8. Therefore, the sum of distance of P(= 8) from all points is (8 – 1) + (8 – 3) + (8 – 6) + (8 – 7) + (11 – 8) = 18( =K) which is equal to the given value K and the point 8 lies between the first(= 1) and the last(= 11) point.Input: arr[] = {-10, -2, 1, 2}, K= 29
Output: -9
Approach: The given problem can be solved based on the observation that the sum of distances will be minimum at the median of the array and the distance increases when moved from the median towards any of the extremities. So, the idea is to perform a binary search on the both the halves of the array and check if any point has a distance equal to K. Follow the steps below to solve the problem:
- Declare a function that calculates the sum of distances of all points from a given point.
- Perform a binary search on the right half of the array as:
- If the value of N is odd, then update the value of left as arr[N / 2]. Otherwise, update the value of left as arr[N / 2 – 1] + 1.
- If the value of N is even, then update the value of right as arr[N – 1].
- Find the sum of distances say temp from mid = (left + right) / 2 and check if the value of temp is equal to K or not. IF found to be true, then print the value of mid as the result.
- If the value of K < temp, then update the value of right as mid – 1. Otherwise, update the value of left as mid + 1.
- Perform a binary search on the left half of the array:
- Set the value of left = arr[0] and right = arr[N / 2] – 1.
- Find the sum of distances say temp from mid = (left + right) / 2 and check if temp is equal to K or not. If found to be true, then print the value of mid as the result.
- If the value of K > temp, then update the value of right = mid – 1. Otherwise, update the value of left = mid + 1.
- If there is no value found in the left and right half then print “-1” as the result.
Below is the implementation of the above approach:
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 pointint 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 Kvoid 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 Codeint 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 approachimport java.lang.*;class GFG{// Function to find the sum of distances// of all points from a given pointpublic 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 Kpublic 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 Codepublic 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 pointdef 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 Kdef 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 Codeif __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 approachusing System;class GFG{// Function to find the sum of distances// of all points from a given pointpublic 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 Kpublic 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 Codepublic 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 pointfunction 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 Kfunction 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 Codevar arr = [ 1, 3, 6, 7, 11 ];var K = 18;var N = arr.length;findPoint(arr, N, K);// This code is contributed by bgangwar59</script> |
Output:
8
Time Complexity: O(N * log2(M – m)) where M is maximum value and m is minimum value of the array.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
