Given an array cell[] of N elements, which represent the positions of the cells in a prison. Also, given an integer P which is the number of prisoners, the task is to place all the prisoners in the cells in an ordered manner such that the minimum distance between any two prisoners is as large as possible. Finally, print the maximized distance.
Examples:Â
Input: cell[] = {1, 2, 8, 4, 9}, P = 3Â
Output: 3Â
The three prisoners will be placed at the cellsÂ
numbered 1, 4 and 8 with the minimum distance 3Â
which is the maximum possible.
Input: cell[] = {10, 12, 18}, P = 2Â
Output: 8Â
The three possible placements are {10, 12}, {10, 18} and {12, 18}.Â
Approach: This problem can be solved using binary search. As the minimum distance between two cells in which prisoners will be kept has to be maximized, the search space will be of distance, starting from 0 (if two prisoners are kept in the same cell) and ending at cell[N – 1] – cell[0] (if one prisoner is kept in the first cell, and the other one is kept in the last cell).Â
Initialize L = 0 and R = cell[N – 1] – cell[0] then apply the binary search. For every mid, check whether the prisoners can be placed such that the minimum distance between any two prisoners is at least midÂ
Â
- If yes then try to increase this distance in order to maximize the answer and check again.
- If not then try to decrease the distance.
- Finally, print the maximized distance.
Below is the implementation of the above approach:Â
Â
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;Â
// Function that returns true if the prisoners// can be placed such that the minimum distance// between any two prisoners is at least sepbool canPlace(int a[], int n, int p, int sep){    // Considering the first prisoner    // is placed at 1st cell    int prisoners_placed = 1;Â
    // If the first prisoner is placed at    // the first cell then the last_prisoner_placed    // will be the first prisoner placed    // and that will be in cell[0]    int last_prisoner_placed = a[0];Â
    for (int i = 1; i < n; i++) {        int current_cell = a[i];Â
        // Checking if the prisoner can be        // placed at ith cell or not        if (current_cell - last_prisoner_placed >= sep) {            prisoners_placed++;            last_prisoner_placed = current_cell;Â
            // If all the prisoners got placed            // then return true            if (prisoners_placed == p) {                return true;            }        }    }Â
    return false;}Â
// Function to return the maximized distanceint maxDistance(int cell[], int n, int p){Â
    // Sort the array so that binary    // search can be applied on it    sort(cell, cell + n);Â
    // Minimum possible distance    // for the search space    int start = 0;Â
    // Maximum possible distance    // for the search space    int end = cell[n - 1] - cell[0];Â
    // To store the result    int ans = 0;Â
    // Binary search    while (start <= end) {        int mid = start + ((end - start) / 2);Â
        // If the prisoners can be placed such that        // the minimum distance between any two        // prisoners is at least mid        if (canPlace(cell, n, p, mid)) {Â
            // Update the answer            ans = mid;            start = mid + 1;        }        else {            end = mid - 1;        }    }Â
    return ans;}Â
// Driver codeint main(){Â Â Â Â int cell[] = { 1, 2, 8, 4, 9 };Â Â Â Â int n = sizeof(cell) / sizeof(int);Â Â Â Â int p = 3;Â
    cout << maxDistance(cell, n, p);Â
    return 0;} |
Java
// Java implementation of the approach import java.util.*;Â
class GFG {Â
    // Function that returns true if the prisoners     // can be placed such that the minimum distance     // between any two prisoners is at least sep     static boolean canPlace(int a[], int n, int p, int sep)     {         // Considering the first prisoner         // is placed at 1st cell         int prisoners_placed = 1;              // If the first prisoner is placed at         // the first cell then the last_prisoner_placed         // will be the first prisoner placed         // and that will be in cell[0]         int last_prisoner_placed = a[0];              for (int i = 1; i < n; i++)         {             int current_cell = a[i];                  // Checking if the prisoner can be             // placed at ith cell or not             if (current_cell - last_prisoner_placed >= sep)             {                 prisoners_placed++;                 last_prisoner_placed = current_cell;                      // If all the prisoners got placed                 // then return true                 if (prisoners_placed == p)                 {                     return true;                 }             }         }              return false;     }          // Function to return the maximized distance     static int maxDistance(int cell[], int n, int p)     {              // Sort the array so that binary         // search can be applied on it         Arrays.sort(cell);              // Minimum possible distance         // for the search space         int start = 0;              // Maximum possible distance         // for the search space         int end = cell[n - 1] - cell[0];              // To store the result         int ans = 0;              // Binary search         while (start <= end)         {             int mid = start + ((end - start) / 2);                  // If the prisoners can be placed such that             // the minimum distance between any two             // prisoners is at least mid             if (canPlace(cell, n, p, mid))            {                      // Update the answer                 ans = mid;                 start = mid + 1;             }             else            {                 end = mid - 1;             }         }         return ans;     }          // Driver code     public static void main (String[] args)    {         int cell[] = { 1, 2, 8, 4, 9 };         int n = cell.length;         int p = 3;              System.out.println(maxDistance(cell, n, p));          } }Â
// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approachÂ
# Function that returns true if the prisoners# can be placed such that the minimum distance# between any two prisoners is at least sepdef canPlace(a, n, p, sep):         # Considering the first prisoner    # is placed at 1st cell    prisoners_placed = 1Â
    # If the first prisoner is placed at    # the first cell then the last_prisoner_placed    # will be the first prisoner placed    # and that will be in cell[0]    last_prisoner_placed = a[0]Â
    for i in range(1, n):        current_cell = a[i]Â
        # Checking if the prisoner can be        # placed at ith cell or not        if (current_cell - last_prisoner_placed >= sep):            prisoners_placed += 1            last_prisoner_placed = current_cellÂ
            # If all the prisoners got placed            # then return true            if (prisoners_placed == p):                return TrueÂ
    return FalseÂ
# Function to return the maximized distancedef maxDistance(cell, n, p):Â
    # Sort the array so that binary    # search can be applied on it    cell = sorted(cell)Â
    # Minimum possible distance    # for the search space    start = 0Â
    # Maximum possible distance    # for the search space    end = cell[n - 1] - cell[0]Â
    # To store the result    ans = 0Â
    # Binary search    while (start <= end):        mid = start + ((end - start) // 2)Â
        # If the prisoners can be placed such that        # the minimum distance between any two        # prisoners is at least mid        if (canPlace(cell, n, p, mid)):Â
            # Update the answer            ans = mid            start = mid + 1        else :            end = mid - 1Â
    return ansÂ
# Driver codecell= [1, 2, 8, 4, 9]n = len(cell)p = 3Â
print(maxDistance(cell, n, p))Â
# This code is contributed by mohit kumar 29 |
C#
// C# implementation of the approach using System;using System.Collections; Â
class GFG { Â
    // Function that returns true if the prisoners     // can be placed such that the minimum distance     // between any two prisoners is at least sep     static bool canPlace(int []a, int n,                          int p, int sep)     {         // Considering the first prisoner         // is placed at 1st cell         int prisoners_placed = 1;              // If the first prisoner is placed at         // the first cell then the last_prisoner_placed         // will be the first prisoner placed         // and that will be in cell[0]         int last_prisoner_placed = a[0];              for (int i = 1; i < n; i++)         {             int current_cell = a[i];                  // Checking if the prisoner can be             // placed at ith cell or not             if (current_cell - last_prisoner_placed >= sep)             {                 prisoners_placed++;                 last_prisoner_placed = current_cell;                      // If all the prisoners got placed                 // then return true                 if (prisoners_placed == p)                 {                     return true;                 }             }         }         return false;     }          // Function to return the maximized distance     static int maxDistance(int []cell, int n, int p)     {              // Sort the array so that binary         // search can be applied on it         Array.Sort(cell);              // Minimum possible distance         // for the search space         int start = 0;              // Maximum possible distance         // for the search space         int end = cell[n - 1] - cell[0];              // To store the result         int ans = 0;              // Binary search         while (start <= end)         {             int mid = start + ((end - start) / 2);                  // If the prisoners can be placed such that             // the minimum distance between any two             // prisoners is at least mid             if (canPlace(cell, n, p, mid))             {                      // Update the answer                 ans = mid;                 start = mid + 1;             }             else            {                 end = mid - 1;             }         }         return ans;     }          // Driver code     public static void Main()     {         int []cell = { 1, 2, 8, 4, 9 };         int n = cell.Length;         int p = 3;              Console.WriteLine(maxDistance(cell, n, p));     } } Â
// This code is contributed by AnkitRai01 |
Javascript
<script>// javascript implementation of the approach Â
    // Function that returns true if the prisoners    // can be placed such that the minimum distance    // between any two prisoners is at least sep    function canPlace(a , n , p , sep)     {             // Considering the first prisoner        // is placed at 1st cell        var prisoners_placed = 1;Â
        // If the first prisoner is placed at        // the first cell then the last_prisoner_placed        // will be the first prisoner placed        // and that will be in cell[0]        var last_prisoner_placed = a[0];Â
        for (i = 1; i < n; i++)        {            var current_cell = a[i];Â
            // Checking if the prisoner can be            // placed at ith cell or not            if (current_cell - last_prisoner_placed >= sep)            {                prisoners_placed++;                last_prisoner_placed = current_cell;Â
                // If all the prisoners got placed                // then return true                if (prisoners_placed == p)                 {                    return true;                }            }        }Â
        return false;    }Â
    // Function to return the maximized distance    function maxDistance(cell , n , p)    {Â
        // Sort the array so that binary        // search can be applied on it        cell.sort();Â
        // Minimum possible distance        // for the search space        var start = 0;Â
        // Maximum possible distance        // for the search space        var end = cell[n - 1] - cell[0];Â
        // To store the result        var ans = 0;Â
        // Binary search        while (start <= end)        {            var mid = start + parseInt(((end - start) / 2));Â
            // If the prisoners can be placed such that            // the minimum distance between any two            // prisoners is at least mid            if (canPlace(cell, n, p, mid))            {Â
                // Update the answer                ans = mid;                start = mid + 1;            }            else            {                end = mid - 1;            }        }        return ans;    }Â
    // Driver code        var cell = [ 1, 2, 8, 4, 9 ];        var n = cell.length;        var p = 3;Â
        document.write(maxDistance(cell, n, p));Â
// This code is contributed by Rajput-Ji</script> |
Output:Â
3
Â
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!
