Given C magnets and an array arr[] representing N index positions where C ? N. The task is to place these magnets at these available indices in such a way that the distance between the two nearest magnets is as large as possible.
Examples:
Input: C = 4, arr[] = {1, 2, 5, 8, 10, 18}
Output: 4
We can place 4 magnets to positions 1, 5, 10, 18 so maximum distance is minimum of ( dist(1, 5), dist(5, 10), dist(10, 18) ) = dist(1, 5) = 4.
And it will be the maximum possible distance between two nearest magnets.
Input: C = 3, arr[] = {5, 7, 11, 20, 23}
Output: 6
We can place 3 magnets to positions 5, 11, 23 so answer will be minimum of ( dist(5, 11), dist(11, 23) ) = dist(5, 11) = 6.
Naive approach: Find all possible positions of magnets that is C(n, c) possible ways and find one that maximizes the distance between two magnets, where C(n, c) is selecting c objects from n given objects.
Efficient approach: Let mx be the maximum possible distance, therefore all x greater than 0 and less than mx will also allow placing magnets but for all y greater than mx, it will not be possible to place the magnets. Therefore we can use binary search to find the maximum possible distance.
Since our answer will always lie between 0 and the maximum index among the given N indices. Therefore apply binary search and find the middle value between the lowest and highest values say ‘mid’, make a function that will check if it is possible to place C magnets assuming ‘mid’ as the maximum possible distance.
Overall time complexity will be O(nlog(n)) since binary search will take O(log(n)) and O(n) for checking that if it is possible to place all C magnets.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible// to place C magnets assuming mid as// maximum possible distancebool isPossible(int arr[], int n, int C, int mid){ // Variable magnet will store count of magnets // that got placed and currPosition will store // the position of last placed magnet int magnet = 1, currPosition = arr[0]; for (int i = 1; i < n; i++) { // If difference between current index and // last placed index is greater than or equal to mid // it will allow placing magnet to this index if (arr[i] - currPosition >= mid) { magnet++; // Now this index will become // last placed index currPosition = arr[i]; // If count of magnets placed becomes C if (magnet == C) return true; } } // If count of placed magnet is // less than C then return false return false;}// Function for modified binary searchint binarySearch(int n, int C, int arr[]){ int lo, hi, mid, ans; // Sort the indices in ascending order sort(arr, arr + n); // Minimum possible distance lo = 0; // Maximum possible distance hi = arr[n - 1]; ans = 0; // Run the loop until lo becomes // greater than hi while (lo <= hi) { mid = (lo + hi) / 2; // If not possible, decrease value of hi if (!isPossible(arr, n, C, mid)) hi = mid - 1; else { // Update the answer ans = max(ans, mid); lo = mid + 1; } } // Return maximum possible distance return ans;}// Driver codeint main(){ int C = 4; int arr[] = { 1, 2, 5, 8, 10, 18 }; int n = sizeof(arr) / sizeof(arr[0]); cout << binarySearch(n, C, arr) << endl; return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function to check if it is possible// to place C magnets assuming mid as// maximum possible distancestatic boolean isPossible(int []arr, int n, int C, int mid){ // Variable magnet will store count of magnets // that got placed and currPosition will store // the position of last placed magnet int magnet = 1, currPosition = arr[0]; for (int i = 1; i < n; i++) { // If difference between current index and // last placed index is greater than or equal to mid // it will allow placing magnet to this index if (arr[i] - currPosition >= mid) { magnet++; // Now this index will become // last placed index currPosition = arr[i]; // If count of magnets placed becomes C if (magnet == C) return true; } } // If count of placed magnet is // less than C then return false return false;}// Function for modified binary searchstatic int binarySearch(int n, int C, int []arr){ int lo, hi, mid, ans; // Sort the indices in ascending order Arrays.sort(arr); // Minimum possible distance lo = 0; // Maximum possible distance hi = arr[n - 1]; ans = 0; // Run the loop until lo becomes // greater than hi while (lo <= hi) { mid = (lo + hi) / 2; // If not possible, decrease value of hi if (!isPossible(arr, n, C, mid)) hi = mid - 1; else { // Update the answer ans = Math.max(ans, mid); lo = mid + 1; } } // Return maximum possible distance return ans;}// Driver codepublic static void main(String args[]){ int C = 4; int []arr = { 1, 2, 5, 8, 10, 18 }; int n = arr.length; System.out.println(binarySearch(n, C, arr));}}// This code is contributed by Akanksha Rai |
Python3
# Python 3 implementation of the approach# Function to check if it is possible# to place C magnets assuming mid as# maximum possible distancedef isPossible(arr, n, C, mid): # Variable magnet will store count of # magnets that got placed and # currPosition will store the position # of last placed magnet magnet = 1 currPosition = arr[0] for i in range(1, n): # If difference between current index # and last placed index is greater than # or equal to mid it will allow placing # magnet to this index if (arr[i] - currPosition >= mid): magnet += 1 # Now this index will become # last placed index currPosition = arr[i] # If count of magnets placed becomes C if (magnet == C): return True # If count of placed magnet is # less than C then return false return False# Function for modified binary searchdef binarySearch(n, C, arr): # Sort the indices in ascending order arr.sort(reverse = False) # Minimum possible distance lo = 0 # Maximum possible distance hi = arr[n - 1] ans = 0 # Run the loop until lo becomes # greater than hi while (lo <= hi): mid = int((lo + hi) / 2) # If not possible, decrease value of hi if (isPossible(arr, n, C, mid) == False): hi = mid - 1 else: # Update the answer ans = max(ans, mid) lo = mid + 1 # Return maximum possible distance return ans# Driver codeif __name__ == '__main__': C = 4 arr = [1, 2, 5, 8, 10, 18] n = len(arr) print(binarySearch(n, C, arr))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG{// Function to check if it is possible// to place C magnets assuming mid as// maximum possible distancestatic bool isPossible(int []arr, int n, int C, int mid){ // Variable magnet will store count of magnets // that got placed and currPosition will store // the position of last placed magnet int magnet = 1, currPosition = arr[0]; for (int i = 1; i < n; i++) { // If difference between current index and // last placed index is greater than or equal to mid // it will allow placing magnet to this index if (arr[i] - currPosition >= mid) { magnet++; // Now this index will become // last placed index currPosition = arr[i]; // If count of magnets placed becomes C if (magnet == C) return true; } } // If count of placed magnet is // less than C then return false return false;}// Function for modified binary searchstatic int binarySearch(int n, int C, int []arr){ int lo, hi, mid, ans; // Sort the indices in ascending order Array.Sort(arr); // Minimum possible distance lo = 0; // Maximum possible distance hi = arr[n - 1]; ans = 0; // Run the loop until lo becomes // greater than hi while (lo <= hi) { mid = (lo + hi) / 2; // If not possible, decrease value of hi if (!isPossible(arr, n, C, mid)) hi = mid - 1; else { // Update the answer ans = Math.Max(ans, mid); lo = mid + 1; } } // Return maximum possible distance return ans;}// Driver codestatic void Main(){ int C = 4; int []arr = { 1, 2, 5, 8, 10, 18 }; int n = arr.Length; Console.WriteLine(binarySearch(n, C, arr));}}// This code is contributed by chandan_jnu |
PHP
<?php// PHP implementation of the approach// Function to check if it is possible// to place C magnets assuming mid as// maximum possible distancefunction isPossible($arr, $n, $C, $mid){ // Variable magnet will store count of magnets // that got placed and currPosition will store // the position of last placed magnet $magnet = 1; $currPosition = $arr[0]; for ($i = 1; $i < $n; $i++) { // If difference between current index and // last placed index is greater than or equal to mid // it will allow placing magnet to this index if ($arr[$i] - $currPosition >= $mid) { $magnet++; // Now this index will become // last placed index $currPosition = $arr[$i]; // If count of magnets placed becomes C if ($magnet == $C) return true; } } // If count of placed magnet is // less than C then return false return false;}// Function for modified binary searchfunction binarySearch($n, $C, $arr){ // Sort the indices in ascending order sort($arr, 0); // Minimum possible distance $lo = 0; // Maximum possible distance $hi = $arr[$n - 1]; $ans = 0; // Run the loop until lo becomes // greater than hi while ($lo <= $hi) { $mid = ($lo + $hi) / 2; // If not possible, decrease value of hi if (!isPossible($arr, $n, $C, $mid)) $hi = $mid - 1; else { // Update the answer $ans = max($ans, $mid); $lo = $mid + 1; } } // Return maximum possible distance return $ans;}// Driver code$C = 4;$arr = array(1, 2, 5, 8, 10, 18);$n = sizeof($arr);echo binarySearch($n, $C, $arr) . "\n";// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// Javascript implementation of the approach// Function to check if it is possible// to place C magnets assuming mid as// maximum possible distancefunction isPossible(arr, n, C, mid){ // Variable magnet will store count of magnets // that got placed and currPosition will store // the position of last placed magnet let magnet = 1; currPosition = arr[0]; for (let i = 1; i < n; i++) { // If difference between current index and // last placed index is greater than or equal to mid // it will allow placing magnet to this index if (arr[i] - currPosition >= mid) { magnet++; // Now this index will become // last placed index currPosition = arr[i]; // If count of magnets placed becomes C if (magnet == C) return true; } } // If count of placed magnet is // less than C then return false return false;}// Function for modified binary searchfunction binarySearch(n, C, arr){ // Sort the indices in ascending order arr.sort((a, b) => a - b); // Minimum possible distance let lo = 0; // Maximum possible distance let hi = arr[n - 1]; let ans = 0; // Run the loop until lo becomes // greater than hi while (lo <= hi) { mid = Math.floor((lo + hi) / 2); // If not possible, decrease value of hi if (!isPossible(arr, n, C, mid)) hi = mid - 1; else { // Update the answer ans = Math.max(ans, mid); lo = mid + 1; } } // Return maximum possible distance return ans;}// Driver codelet C = 4;let arr = new Array(1, 2, 5, 8, 10, 18);let n = arr.length;document.write(binarySearch(n, C, arr) + "<br>");// This code is contributed by _saurabh_jaiswal</script> |
Output:
4
Time Complexity: O(n * log(n))
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!
