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

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {2, 4, 8, 10}, K = 1Output:2Explanation: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 = 9Output: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 ^{8}]** 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^{8}**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^{14}.**Auxiliary Space:** O(1)