Optimal Placement of People in Circular Locations
Given two integers N and K. Consider N locations which are circularly connected (Formally, after the Nth location the next location is 1st location). Then your task is to place K people into N circular locations such that the maximum distance between two consecutive persons is as less as possible. Also, output the minimum number of consecutive pairs satisfying this distance.
Note: The locations are seperated by unit distance.
Examples:
Input: N = 6, M = 3
Output: 2 3
Explanation: Consider there are N = 6 circularly connected locations. Then, place 3 persons at 1st, 3rd and 5th locations respectively. It is clearly visible that that between any two consecutive persons is 2. Which is minimum possible. The number of pairs satisfying this distance is 3, (1, 3) (3, 5) and (5, 1). All pairs have distance as 2.
Input: N = 10, M = 6
Output: 2 4
Explanation: Consider there are N = 10 circularly connected locations. Then, place 6 persons at 1st, 2nd, 4th, 6th, 8th and 10th location respectively. The maximum distance between any 2 consecutive persons is 2. The maximum distance is 2. Which is minimum possible. The number of pairs satisfying this distance is 3, (1, 3) (3, 5) and (5, 1). All pairs have distance as 2. There shall be at least 4 pairs of separated by this distance, which are (2, 4) (4, 6) (6, 8) and (8, 10).
Approach: Implement the idea below to solve the problem
The problem is observation based. Now, let us solve the problem by calculating the minimum possible distance denoted by A and the minimum number of pairs of adjacent people separated by this distance as B.
Formula used:
- Minimum possible distance (A): The formula 1 + (N – 1)/K is used to calculate the minimum possible distance between any two persons. The reason is:
- We subtract 1 from N because we already have a person at the first location. So, the remaining locations to place servers are N-1.
- We divide N – 1 by K to distribute the remaining locations evenly among the persons.
- We add 1 to ensure that each person is at least one unit apart from each other.
- Minimum number of pairs (B): The formula (N % K) is used to calculate the minimum number of pairs of adjacent persons separated by this distance. The reason is:
- When we divide N by K, we might have some locations left over. These are the locations that cannot be evenly distributed among the persons.
- The remainder of this division (N % K) gives us the number of extra locations, which will be closer to some persons than others. This is the minimum number of pairs of adjacent persons separated by this distance.
If there are no extra locations (B is zero), it means that the persons are perfectly distributed, so we set B to K, as each person will have an adjacent server at this minimum distance.
This approach provides a more efficient solution to the problem, As it directly calculates the results instead of iterating over all possible arrangements of persons.
Steps were taken to solve the problem:
- Declare two variables let say A and B for storing the minimum possible distance and count of pairs satisfying minimum distance.
- Set, A = 1 + (N – 1)/K
- Set, B = N%K
- If(B == 0)
- B = K
- Output A and B.
Code to implement the approach:
C++
#include <iostream> using namespace std; // Function to output the minimum distance and number of pairs void Minimized_distance( int N, int K) { // Implementation of discussed formulas int A = 1 + (N - 1) / K; int B = N % K; if (B == 0) B = K; // Printing the minimized distance and number of pairs cout << A << " " << B << endl; } // Driver Function int main() { // Inputs int N = 10, K = 4; // Function call Minimized_distance(N, K); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver Class public class GFG { // Driver Function public static void main(String[] args) { // Inputs int N = 10 , K = 4 ; // Function call Minimized_distance(N, K); } // Method to output the minimum Minimum // distance and number of pairs // satisfying such distance public static void Minimized_distance( int N, int K) { // Implementation of discussed formulas int A = 1 + (N - 1 ) / K; int B = N % K; if (B == 0 ) B = K; // Printing the minimized distance and // number of pairs System.out.println(A + " " + B); } } |
Python3
# Python Code Addition def minimized_distance(N, K): A = 1 + (N - 1 ) / / K B = N % K if B = = 0 : B = K print (A, B) N = 10 K = 4 minimized_distance(N, K) # This code is contributed by Sakshi |
C#
using System; public class GFG { // Main Method public static void Main( string [] args) { // Inputs int N = 10, K = 4; // Function call MinimizedDistance(N, K); } // Method to output the minimum Minimum // distance and number of pairs // satisfying such distance public static void MinimizedDistance( int N, int K) { // Implementation of discussed formulas int A = 1 + (N - 1) / K; int B = N % K; if (B == 0) B = K; // Printing the minimized distance and // number of pairs Console.WriteLine(A + " " + B); } } |
Javascript
// Function to output the minimum distance and number of pairs function Minimized_distance(N, K) { // Implementation of discussed formulas let A = 1 + Math.floor((N - 1) / K); let B = N % K; if (B === 0) { B = K; } // Printing the minimized distance and number of pairs console.log(A + " " + B); } // Driver Function function main() { // Inputs let N = 10, K = 4; // Function call Minimized_distance(N, K); } // Calling the main function main(); |
3 2
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us