Given an integer array A[] of length N and an integer K. The task is to find K distinct integral points that are not present in the given array such that the sum of their distances from the nearest point in A[] is minimized.
An integral point is defined as the point with both the coordinates as integers. Also, in the x-axis, we don’t need to consider y-coordinate because y-coordinated of all the points is equal to zero.
Examples:
Input: A[] = { -1, 4, 6 }, K = 3
Output: -2, 0, 3
Explanation:
Nearest point for -2 in A[] is -1 -> distance = 1
Nearest point for 0 in A[] is -1 -> distance = 1
Nearest point for 3 in A[] is 4 -> distance = 1
Total distance = 1 + 1 + 1 = 3 which is minimum possible distance.
Other results are also possible with the same minimum distance.
Input: A[] = { 0, 1, 3, 4 }, K = 5
Output: -1, 2, 5, -2, 6
Explanation:
Nearest point for -1 in A[] is 0 -> distance = 1
Nearest point for 2 in A[] is 3 -> distance = 1
Nearest point for 5 in A[] is 4 -> distance = 1
Nearest point for -2 in A[] is 0 -> distance = 2
Nearest point for 6 in A[] is 4 -> distance = 2
Total distance = 2 + 1 + 1 + 1 + 2 = 7 which is minimum possible distance.
Approach: We will solve this problem by using the concept of Breadth First Search.
- We will initially assume the given set of integers as the root element and push it in Queue and Hash.
- Then for any element say X, we will simply check if (X-1) or (X+1) is encountered or not using a hashmap. If any of them are not encountered so far then we push that element in our answer array and queue and hash as well.
- Repeat this until we encountered K new elements.
Below is the implementation of the above approach.
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to find points at // minimum distance void minDistancePoints( int A[], int K, int n) { // Hash to store points // that are encountered map< int , int > m; // Queue to store initial // set of points queue< int > q; for ( int i = 0; i < n; ++i) { m[A[i]] = 1; q.push(A[i]); } // Vector to store integral // points vector< int > ans; // Using bfs to visit nearest // points from already // visited points while (K > 0) { // Get first element from // queue int x = q.front(); q.pop(); // Check if (x-1) is not // encountered so far if (!m[x - 1] && K > 0) { // Update hash with // this new element m[x - 1] = 1; // Insert (x-1) into // queue q.push(x - 1); // Push (x-1) as // new element ans.push_back(x - 1); // Decrement counter // by 1 K--; } // Check if (x+1) is not // encountered so far if (!m[x + 1] && K > 0) { // Update hash with // this new element m[x + 1] = 1; // Insert (x+1) into // queue q.push(x + 1); // Push (x+1) as // new element ans.push_back(x + 1); // Decrement counter // by 1 K--; } } // Print result array for ( auto i : ans) cout << i << " " ; } // Driver code int main() { int A[] = { -1, 4, 6 }; int K = 3; int n = sizeof (A) / sizeof (A[0]); minDistancePoints(A, K, n); return 0; } |
Java
// Java implementation of above approach import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Queue; class Geeks{ // Function to find points at // minimum distance static void minDistancePoints( int A[], int K, int n) { // Hash to store points // that are encountered Map<Integer, Boolean> m = new HashMap<Integer, Boolean>(); // Queue to store initial // set of points Queue<Integer> q = new LinkedList<Integer>(); for ( int i = 0 ; i < n; ++i) { m.put(A[i], true ); q.add(A[i]); } // List to store integral // points LinkedList<Integer> ans = new LinkedList<Integer>(); // Using bfs to visit nearest // points from already // visited points while (K > 0 ) { // Get first element from // queue int x = q.poll(); // Check if (x-1) is not // encountered so far if (!m.containsKey(x - 1 ) && K > 0 ) { // Update hash with // this new element m.put(x - 1 , true ); // Insert (x-1) into // queue q.add(x - 1 ); // Push (x-1) as // new element ans.add(x - 1 ); // Decrement counter // by 1 K--; } // Check if (x+1) is not // encountered so far if (!m.containsKey(x + 1 ) && K > 0 ) { // Update hash with // this new element m.put(x + 1 , true ); // Insert (x+1) into // queue q.add(x + 1 ); // Push (x+1) as // new element ans.add(x + 1 ); // Decrement counter // by 1 K--; } } // Print result array for (Integer i : ans) System.out.print(i + " " ); } // Driver code public static void main(String[] args) { int A[] = new int [] { - 1 , 4 , 6 }; int K = 3 ; int n = A.length; minDistancePoints(A, K, n); } } // This code is contributed by Rajnis09 |
Python3
# Python 3 implementation # of above approach # Function to find points # at minimum distance def minDistancePoints(A, K, n): # Hash to store points # that are encountered m = {} # Queue to store initial # set of points q = [] for i in range (n): m[A[i]] = 1 q.append(A[i]) # Vector to store # integral points ans = [] # Using bfs to visit nearest # points from already # visited points while (K > 0 ): # Get first element from # queue x = q[ 0 ] q = q[ 1 ::] # Check if (x-1) is not # encountered so far if ((x - 1 ) not in m and K > 0 ): # Update hash with # this new element m[x - 1 ] = m.get(x - 1 , 0 ) + 1 # Insert (x-1) into # queue q.append(x - 1 ) # Push (x-1) as # new element ans.append(x - 1 ) # Decrement counter # by 1 K - = 1 # Check if (x+1) is not # encountered so far if ((x + 1 ) not in m and K > 0 ): # Update hash with # this new element m[x + 1 ] = m.get(x + 1 , 0 ) + 1 # Insert (x+1) into # queue q.append(x + 1 ) # Push (x+1) as # new element ans.append(x + 1 ) # Decrement counter # by 1 K - = 1 # Print result array for i in ans: print (i, end = " " ) # Driver code if __name__ = = '__main__' : A = [ - 1 , 4 , 6 ] K = 3 n = len (A) minDistancePoints(A, K, n) # This code is contributed by bgangwar59 |
C#
// C# implementation of above approach using System; using System.Collections.Generic; class GFG{ // Function to find points at // minimum distance static void minDistancePoints( int []A, int K, int n) { // Hash to store points // that are encountered Dictionary< int , Boolean> m = new Dictionary< int , Boolean>(); // Queue to store initial // set of points Queue< int > q = new Queue< int >(); for ( int i = 0; i < n; ++i) { m.Add(A[i], true ); q.Enqueue(A[i]); } // List to store integral // points List< int > ans = new List< int >(); // Using bfs to visit nearest // points from already // visited points while (K > 0) { // Get first element from // queue int x = q.Dequeue(); // Check if (x-1) is not // encountered so far if (!m.ContainsKey(x - 1) && K > 0) { // Update hash with // this new element m.Add(x - 1, true ); // Insert (x-1) into // queue q.Enqueue(x - 1); // Push (x-1) as // new element ans.Add(x - 1); // Decrement counter // by 1 K--; } // Check if (x+1) is not // encountered so far if (!m.ContainsKey(x + 1) && K > 0) { // Update hash with // this new element m.Add(x + 1, true ); // Insert (x+1) into // queue q.Enqueue(x + 1); // Push (x+1) as // new element ans.Add(x + 1); // Decrement counter // by 1 K--; } } // Print result array foreach ( int i in ans) Console.Write(i + " " ); } // Driver code public static void Main(String[] args) { int []A = new int [] { -1, 4, 6 }; int K = 3; int n = A.Length; minDistancePoints(A, K, n); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // Javascript implementation of above approach // Function to find points at // minimum distance function minDistancePoints(A, K, n) { // Hash to store points // that are encountered let m = new Map(); // Queue to store initial // set of points let q = []; for (let i = 0; i < n; ++i) { m.set(A[i], true ); q.push(A[i]); } // List to store integral // points let ans = []; // Using bfs to visit nearest // points from already // visited points while (K > 0) { // Get first element from // queue let x = q.shift(); // Check if (x-1) is not // encountered so far if (!m.has(x - 1) && K > 0) { // Update hash with // this new element m.set(x - 1, true ); // Insert (x-1) into // queue q.push(x - 1); // Push (x-1) as // new element ans.push(x - 1); // Decrement counter // by 1 K--; } // Check if (x+1) is not // encountered so far if (!m.has(x + 1) && K > 0) { // Update hash with // this new element m.set(x + 1, true ); // Insert (x+1) into // queue q.push(x + 1); // Push (x+1) as // new element ans.push(x + 1); // Decrement counter // by 1 K--; } } // Print result array for (let i = 0; i < ans.length; i++) document.write(ans[i] + " " ); } let A = [ -1, 4, 6 ]; let K = 3; let n = A.length; minDistancePoints(A, K, n); // This code is contributed by divyeshrabadiya07. </script> |
-2 0 3
Time Complexity: O(M*log(M)), where M = N + K.
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!