Grouping robots on cartesian plane
In a 2D array robots[][], and an integer value K, where robots[i][j] represent the position of a robot on the cartesian plan. The task is to count the number of minimum groups that are formed by the robots such that the distance between robots in a group should be <= K.
Note: If two robots, ‘a’ and ‘b’, belong to the same group, and ‘a’ and ‘d’ also belong to the same group, then ‘b‘ and ‘d’ are to be considered part of the same group as well.
Examples:
Input: robots[][] = {{13, -62}, {3, 3}, {2, 2}}, K = 2
Output: 2
Explanation: There are two groups.
1st group: {{2, 2}, {3, 3}}
2nd group: {{12, -62}}Input: robots[][] = {{13, 26}, {14, 12}, {31, 12}, {14, 29}}, K = 2
Output: 3
Approach (Using Disjoint Set Union):
Initially, consider each robot as a separate and distinct group. Therefore, the initial count of separate groups is equal to ‘N’ (where ‘N’ represents the total number of robots in the robots[][] array). Create pairs of robots from the array ‘robots[][]’. Subsequently, check whether the distance between these robots is less than or equal to ‘K’. If this condition is true, combine the robots into a single group and decrease the count of separate groups by 1.
Steps to solve the problem:
- Iterate over all pairs of robots positions, calculating the distance between them using the distance formula.
- If the distance is less than or equal to ‘K‘, merge the two robots into one group and update the connected component count.
- Return the count of connected components after processing all the pairs of robots.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the parent of a node int find( int x, vector< int >& parent) { if (x == parent[x]) return x; return parent[x] = find(parent[x], parent); } // Function to unite two sets bool union1( int x, int y, vector< int >& parent, vector< int >& rank) { int lx = find(x, parent); int ly = find(y, parent); // Condition of merging if (lx != ly) { if (rank[lx] > rank[ly]) { parent[ly] = lx; } else if (rank[lx] < rank[ly]) { parent[lx] = ly; } else { parent[lx] = ly; rank[ly] += 1; } // Return true for merging two // groups into one groups return true ; } // Return false if robots are // already merged. return false ; } // Function to count the number of groups // formed after grouping the robots int solve(vector<vector< int > >& robots, int k) { int n = robots.size(), // cc is for number of // connected component cc = n; vector< int > parent(n), rank(n); for ( int i = 0; i < n; i++) { parent[i] = i; rank[i] = 1; } // Iterate over all pairs of robot for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { long long x1 = robots[i][0], y1 = robots[i][1]; long long x2 = robots[j][0], y2 = robots[j][1]; // Calculate the distance // between the robots long long x = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // Check the given condition if (x * x <= k * k) { // Merge this pair of robots // into one group bool merge = union1(i, j, parent, rank); // If these robots are getting // merged then reduce the cc by 1; if (merge) cc--; } } } return cc; } // Driver code int main() { vector<vector< int > > robots = { { 13, -62 }, { 3, 3 }, { 2, 2 } }; int K = 2; int result = solve(robots, K); // Function Call cout << result << endl; return 0; } |
Java
import java.util.ArrayList; import java.util.List; public class RobotGroups { // Function to find the parent of a node static int find( int x, List<Integer> parent) { if (x == parent.get(x)) return x; // Path compression: Set the parent of x to the root // to optimize future lookups parent.set(x, find(parent.get(x), parent)); return parent.get(x); } // Function to unite two sets static boolean union( int x, int y, List<Integer> parent, List<Integer> rank) { int lx = find(x, parent); int ly = find(y, parent); // Condition of merging if (lx != ly) { if (rank.get(lx) > rank.get(ly)) { parent.set(ly, lx); } else if (rank.get(lx) < rank.get(ly)) { parent.set(lx, ly); } else { parent.set(lx, ly); rank.set(ly, rank.get(ly) + 1 ); } // Return true for merging two groups into one // group return true ; } // Return false if robots are already merged. return false ; } // Function to count the number of groups formed after // grouping the robots static int solve(List< int []> robots, int k) { int n = robots.size(); // cc is for the number of connected components // (groups) int cc = n; List<Integer> parent = new ArrayList<>(n); List<Integer> rank = new ArrayList<>(n); for ( int i = 0 ; i < n; i++) { parent.add(i); rank.add( 1 ); } // Iterate over all pairs of robots for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { long x1 = robots.get(i)[ 0 ], y1 = robots.get(i)[ 1 ]; long x2 = robots.get(j)[ 0 ], y2 = robots.get(j)[ 1 ]; // Calculate the distance between the robots long x = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // Check the given condition if (x * x <= k * k) { // Merge this pair of robots into one // group boolean merge = union(i, j, parent, rank); // If these robots are getting merged, // then reduce the cc by 1 if (merge) cc--; } } } return cc; } public static void main(String[] args) { List< int []> robots = new ArrayList<>(); robots.add( new int [] { 13 , - 62 }); robots.add( new int [] { 3 , 3 }); robots.add( new int [] { 2 , 2 }); int K = 2 ; int result = solve(robots, K); // Function Call System.out.println(result); } } |
Python3
# Python Implementation # Function to find the parent of a node def find(x, parent): if x = = parent[x]: return x parent[x] = find(parent[x], parent) return parent[x] # Function to unite two sets def union(x, y, parent, rank): lx = find(x, parent) ly = find(y, parent) # Condition of merging if lx ! = ly: if rank[lx] > rank[ly]: parent[ly] = lx elif rank[lx] < rank[ly]: parent[lx] = ly else : parent[lx] = ly rank[ly] + = 1 # Return True for merging two groups into one group return True # Return False if robots are already merged return False # Function to count the number of groups formed after grouping the robots def solve(robots, k): n = len (robots) # cc is for number of connected component cc = n parent = [ 0 ] * n rank = [ 0 ] * n for i in range (n): parent[i] = i rank[i] = 1 # Iterate over all pairs of robots for i in range (n): for j in range (i + 1 , n): x1, y1 = robots[i] x2, y2 = robots[j] # Calculate the distance between the robots x = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) # Check the given condition if x * x < = k * k: # Merge this pair of robots into one group merge = union(i, j, parent, rank) # If these robots are getting merged then reduce the cc by 1 if merge: cc - = 1 return cc # Driver code robots = [[ 13 , - 62 ], [ 3 , 3 ], [ 2 , 2 ]] K = 2 result = solve(robots, K) # Function Call print (result) # This code is contributed by Tapesh (tapeshdua420) |
C#
using System; using System.Collections.Generic; public class RobotGroups { // Function to find the parent of a node static int Find( int x, List< int > parent) { if (x == parent[x]) return x; return parent[x] = Find(parent[x], parent); } // Function to unite two sets static bool Union( int x, int y, List< int > parent, List< int > rank) { int lx = Find(x, parent); int ly = Find(y, parent); // Condition of merging if (lx != ly) { if (rank[lx] > rank[ly]) parent[ly] = lx; else if (rank[lx] < rank[ly]) parent[lx] = ly; else { parent[lx] = ly; rank[ly] += 1; } // Return true for merging two groups into one group return true ; } // Return false if robots are already merged. return false ; } // Function to count the number of groups formed after grouping the robots static int Solve(List<List< int >> robots, int k) { int n = robots.Count; // cc is for number of connected component int cc = n; List< int > parent = new List< int >(); List< int > rank = new List< int >(); for ( int i = 0; i < n; i++) { parent.Add(i); rank.Add(1); } // Iterate over all pairs of robot for ( int i = 0; i < n; i++) { for ( int j = i + 1; j < n; j++) { long x1 = robots[i][0], y1 = robots[i][1]; long x2 = robots[j][0], y2 = robots[j][1]; // Calculate the distance between the robots long x = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // Check the given condition if (x * x <= k * k) { // Merge this pair of robots into one group bool merge = Union(i, j, parent, rank); // If these robots are getting merged then reduce the cc by 1 if (merge) cc--; } } } return cc; } // Driver code public static void Main( string [] args) { List<List< int >> robots = new List<List< int >> { new List< int > { 13, -62 }, new List< int > { 3, 3 }, new List< int > { 2, 2 } }; int K = 2; int result = Solve(robots, K); // Function Call Console.WriteLine(result); } } |
Javascript
// Function to find the root parent of a node in the disjoint set function find(parent, x) { if (x === parent[x]) // If the node's parent is itself, it's the root parent return x; // Path compression: Update the parent of the node and return the root parent return parent[x] = find(parent, parent[x]); } // Function to unite two sets by their root parents function union(x, y, parent, rank) { let lx = find(parent, x); let ly = find(parent, y); if (lx !== ly) { // Union by rank: Attach smaller rank tree under root of higher rank tree if (rank[lx] > rank[ly]) parent[ly] = lx; else if (rank[lx] < rank[ly]) parent[lx] = ly; else { parent[lx] = ly; rank[ly] += 1; // Increase rank if ranks are equal } return true ; // Return true for successful union } return false ; // Return false if nodes are already in the same set } // Function to solve the problem and count groups formed after grouping the robots function solve(robots, k) { let n = robots.length; let cc = n; // cc is for the number of connected components (initially each robot is its own group) let parent = []; // Array to store parent of each node let rank = []; // Array to store rank of each node (for union by rank) // Initialization: Each node is its own parent and has rank 1 for (let i = 0; i < n; i++) { parent.push(i); rank.push(1); } // Iterate over pairs of robots for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { let [x1, y1] = robots[i]; let [x2, y2] = robots[j]; let x = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // Check the distance condition for grouping robots if (x * x <= k * k) { let merge = union(i, j, parent, rank); if (merge) cc--; // Reduce the number of groups if robots are merged } } } return cc; // Return the count of groups formed } // Test case let robots = [ [13, -62], [3, 3], [2, 2] ]; let k = 2; let result = solve(robots, k); console.log(result); // Output the result |
2
Time Complexity: O(N2), where N is the number of robots in the given robots[][] array.
Auxiliary Space: O(N), for storing the parents and rank array in Union Find.