Data Modelling & AI Data Structure & Algorithm

Minimize the maximum distance between adjacent points after adding K points anywhere in between

23 June 2025

2

Given an array arr[] of N integers representing the position of N points along a straight line and an integer K, the task is to find the minimum value of the maximum distance between adjacent points after adding K points anywhere in between, not necessarily on an integer position.

Examples:

Input: arr[] = {2, 4, 8, 10}, K = 1
Output: 2
Explanation: A point at position 6 can be added. So the new array of points become {2, 4, 6, 8, 10} and the maximum distance between two adjacent points is 2 which is minimum possible.

Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, K = 9
Output: 0.5

Approach: The given problem can be solved by using Binary Search. The idea is to perform a binary search on the value D in the range [0, 10⁸] where D represents the value of the maximum distance between the adjacent points after adding K points. Follow the steps below to solve the given problem:

Initialize variables, low = 1 and high = 10⁸, where low represents the lower bound and high represents the upper bound of the binary search.
Create a function isPossible(), which returns the boolean value of whether it is possible to add K points in the array such that the maximum distance between adjacent points is D. It is based on the observation that for two adjacent points (i, j), the number of points required to be placed in their middle such that the maximum distance between them is D = (j -i)/D.
Therefore, traverse the range using the binary search algorithm discussed here, and if for the mid-value D in the range [X, Y], if isPossible(D) is false, then iterate in the upper half of the range i.e, [D, Y]. Otherwise, iterate on the lower half i.e, [X, D].
Iterate a loop until (high – low) > 10^-6.
The value stored in low is the required answer.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to check if it is possible
// to add K points such that the maximum
// distance between adjacent points is D
bool isPossible(double D, int arr[],
                int N, int K)
{
    // Stores the count of point used
    int used = 0;
 
    // Iterate over all given points
    for (int i = 0; i < N - 1; ++i) {
 
        // Add number of points required
        // to be placed between ith
        // and (i+1)th point
        used += (int)((arr[i + 1]
                       - arr[i])
                      / D);
    }
 
    // Return answer
    return used <= K;
}
 
// Function to find the minimum value of
// maximum distance between adjacent points
// after adding K points any where between
double minMaxDist(int stations[], int N, int K)
{
    // Stores the lower bound and upper
    // bound of the given range
    double low = 0, high = 1e8;
 
    // Perform binary search
    while (high - low > 1e-6) {
 
        // Find the middle value
        double mid = (low + high) / 2.0;
 
        if (isPossible(mid, stations, N, K)) {
 
            // Update the current range
            // to lower half
            high = mid;
        }
 
        // Update the current range
        // to upper half
        else {
            low = mid;
        }
    }
 
    return low;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int K = 9;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << minMaxDist(arr, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.math.BigDecimal;
 
class GFG {
 
    // Function to check if it is possible
    // to add K points such that the maximum
    // distance between adjacent points is D
    public static boolean isPossible(double D, int arr[],
                                     int N, int K)
    {
        // Stores the count of point used
        int used = 0;
 
        // Iterate over all given points
        for (int i = 0; i < N - 1; ++i) {
 
            // Add number of points required
            // to be placed between ith
            // and (i+1)th point
            used += (int) ((arr[i + 1] - arr[i]) / D);
        }
 
        // Return answer
        return used <= K;
    }
 
    // Function to find the minimum value of
    // maximum distance between adjacent points
    // after adding K points any where between
    public static double minMaxDist(int stations[], int N, int K) 
    {
       
        // Stores the lower bound and upper
        // bound of the given range
        double low = 0, high = 1e8;
 
        // Perform binary search
        while (high - low > 1e-6) {
 
            // Find the middle value
            double mid = (low + high) / 2.0;
 
            if (isPossible(mid, stations, N, K)) {
 
                // Update the current range
                // to lower half
                high = mid;
            }
 
            // Update the current range
            // to upper half
            else {
                low = mid;
            }
        }
       
        // System.out.printf("Value: %.2f", low);
        return low;
    }
 
    // Driver Code
    public static void main(String args[]) 
    {
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int K = 9;
        int N = arr.length;
 
        System.out.printf("%.1f", minMaxDist(arr, N, K));
    }
}
 
// This code is contributed by _saurabh_jaiswal.

Python3

# Python3 program for the above approach
 
# Function to check if it is possible
# to add K points such that the maximum
# distance between adjacent points is D
def isPossible(D, arr, N, K) :
 
    # Stores the count of point used
    used = 0;
 
    # Iterate over all given points
    for i in range(N - 1) :
 
        # Add number of points required
        # to be placed between ith
        # and (i+1)th point
        used += int((arr[i + 1] - arr[i]) / D);
 
    # Return answer
    return used <= K;
 
# Function to find the minimum value of
# maximum distance between adjacent points
# after adding K points any where between
def minMaxDist(stations, N, K) :
     
    # Stores the lower bound and upper
    # bound of the given range
    low = 0; high = 1e8;
 
    # Perform binary search
    while (high - low > 1e-6) :
 
        # Find the middle value
        mid = (low + high) / 2.0;
 
        if (isPossible(mid, stations, N, K)) :
 
            # Update the current range
            # to lower half
            high = mid;
 
        # Update the current range
        # to upper half
        else :
             
            low = mid;
 
    return round(low, 2);
 
# Driver Code
if __name__ == "__main__" :
 
    arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
    K = 9;
    N = len(arr);
 
    print(minMaxDist(arr, N, K));
     
    # This code is contributed by AnkThon

C#

// C# program for the above approach
using System;
 
public class GFG {
 
    // Function to check if it is possible
    // to add K points such that the maximum
    // distance between adjacent points is D
    public static bool isPossible(double D, int []arr,
                                     int N, int K)
    {
       
        // Stores the count of point used
        int used = 0;
 
        // Iterate over all given points
        for (int i = 0; i < N - 1; ++i) {
 
            // Add number of points required
            // to be placed between ith
            // and (i+1)th point
            used += (int) ((arr[i + 1] - arr[i]) / D);
        }
 
        // Return answer
        return used <= K;
    }
 
    // Function to find the minimum value of
    // maximum distance between adjacent points
    // after adding K points any where between
    public static double minMaxDist(int []stations, int N, int K) 
    {
       
        // Stores the lower bound and upper
        // bound of the given range
        double low = 0, high = 1e8;
 
        // Perform binary search
        while (high - low > 1e-6) {
 
            // Find the middle value
            double mid = (low + high) / 2.0;
 
            if (isPossible(mid, stations, N, K)) {
 
                // Update the current range
                // to lower half
                high = mid;
            }
 
            // Update the current range
            // to upper half
            else {
                low = mid;
            }
        }
       
        // Console.Write("Value: %.2f", low);
        return low;
    }
 
    // Driver Code
    public static void Main(String []args) 
    {
        int []arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int K = 9;
        int N = arr.Length;
 
        Console.Write("{0:F1}", minMaxDist(arr, N, K));
    }
}
 
 
 
// This code is contributed by 29AjayKumar

Javascript

<script>
       // JavaScript Program to implement
       // the above approach
 
       // Function to check if it is possible
       // to add K points such that the maximum
       // distance between adjacent points is D
       function isPossible(D, arr,
           N, K)
       {
        
           // Stores the count of point used
           let used = 0;
 
           // Iterate over all given points
           for (let i = 0; i < N - 1; ++i) {
 
               // Add number of points required
               // to be placed between ith
               // and (i+1)th point
               used += Math.floor((arr[i + 1]
                   - arr[i])
                   / D);
           }
 
           // Return answer
           return used <= K;
       }
 
       // Function to find the minimum value of
       // maximum distance between adjacent points
       // after adding K points any where between
       function minMaxDist(stations, N, K)
       {
        
           // Stores the lower bound and upper
           // bound of the given range
           let low = 0, high = 1e8;
 
           // Perform binary search
           while (high - low > 1e-6) {
 
               // Find the middle value
               let mid = (low + high) / 2;
 
               if (isPossible(mid, stations, N, K)) {
 
                   // Update the current range
                   // to lower half
                   high = mid;
               }
 
               // Update the current range
               // to upper half
               else {
                   low = mid;
               }
           }
 
           return low.toFixed(1);
       }
 
       // Driver Code
       let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
       let K = 9;
       let N = arr.length;
 
       document.write(minMaxDist(arr, N, K));
 
    // This code is contributed by Potta Lokesh
   </script>

Output

0.5

Time Complexity: O(N*log M), where the value of M is 10¹⁴.
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

Minimize the maximum distance between adjacent points after adding K points anywhere in between

C++

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

This 10-in-1 charger is a powerhouse, and it’s a steal at only $30

How to use Satellite SOS on Google Pixel 10

If you’re quick you can now get the Oura Ring for $199

It’s your last chance to score a $50 Samsung credit before tomorrow’s big product announcement

EDITOR PICKS

This 10-in-1 charger is a powerhouse, and it’s a steal at only $30

How to use Satellite SOS on Google Pixel 10

If you’re quick you can now get the Oura Ring for $199

POPULAR POSTS

This 10-in-1 charger is a powerhouse, and it’s a steal at only $30

How to use Satellite SOS on Google Pixel 10

If you’re quick you can now get the Oura Ring for $199

POPULAR CATEGORY

ABOUT US

FOLLOW US