Pick Points from Array to Maximize Minimum Distance in C++

In this problem, we are given an array arr[] of n elements that represent N index positions and there are C magnets. Our task is to print all these magnets in such a way that the distance between the two nearest magnets is as large as possible.

Let’s take an example to understand the problem,

Input − array = { 1, 4, 6,12, 28, 44 } C = 4

Output − 11

To solve this problem, we will use a binary search to maximum distance. We will fix a maximum distance and then placing all magnets between 0 to maximum distance is valid.

Then we will apply a binary search to find middle values and check if placing magnets is possible. If yes then place magnet and treat mid as max distance and follow the same procedure.

Example

Program to show an implementation of our solution,

 Live Demo

#include <iostream>
using namespace std;
bool canPlace(int arr[], int n, int C, int mid){
   int magnet = 1, currPosition = arr[0];
   for (int i = 1; i < n; i++) {
      if (arr[i] - currPosition >= mid) {
         magnet++;
         currPosition = arr[i];
         if (magnet == C)
            return true;
      }
   }
   return false;
}
int minDistMax(int n, int C, int arr[]){
   int lo, hi, mid, ans;
   lo = 0;
   hi = arr[n - 1];
   ans = 0;
   while (lo <= hi) {
      mid = (lo + hi) / 2;
      if (!canPlace(arr, n, C, mid))
         hi = mid - 1;
      else {
         ans = max(ans, mid);
         lo = mid + 1;
      }
   }
   return ans;
}
int main(){
   int C = 4;
   int arr[] = { 1, 4, 6,12, 28, 44 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximised Minimum distance is "<<minDistMax(n, C, arr);
   return 0;
}

Output

Maximised Minimum distance is 11