Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 17 Mar, 2021

Find K Closest Elements

Moderate
Asked in companies
UberFacebookOYO

Problem statement

You are given a sorted array 'A' of length 'N', two integers 'K' and 'X'. Your task is to print 'K' integers closest to 'X', if two integers are at the same distance return the smaller one.

The output should also be in sorted order

Note:
An integer 'a' is closer to 'X' than an integer 'b' if: 
|a - X| < |b - X|  or (  |a - X| == |b - X| and a < b )
For Example:
if X = 4,  3 is closer to 'X' than 9, as |3-4| < |9-4|  i.e., 1 < 5   and if X = 4, 2 and 6 are equally close to it, as |2-4| == |6-4| = 2, but we say 2 is closer to 4 than 6, as 2 is smaller.
Input Format:
The first line of the input contains ‘T’ denoting the number of test cases.

The first line of each test case contains the three integers 'N', 'K', and 'X'.

The second line of each test case contains 'N' space-separated integers of the array 'A'. 
Output Format:
Return the k space-separated integers.

The output of each test case is printed on a new line.
Constraints:
1 <= T <= 5
1 <= N, K <= 5000
1 <= A[i], X <=10^6

Time Limit: 1 second

Approaches

01 Approach

Explanation:

 

  • The key idea is to sort the array using comparator where elements are compared based on the condition: |a - X| < |b - X|  or (  |a - X| == |b - X| and a < b ), where ‘a’ and ‘b’ are two integers in the array.
  • Then pick the 'K' smallest elements from this new sorted array and add them into a new array.
  • Then sort this new array of size 'K', and return it.

 

Algorithm:

 

  • Sort the array using conditions, i.e., compare two integers in it by taking its absolute difference with 'X'. and then taking the smaller one first.
  • Make a list of the first ‘K’ elements and sort them.
  • Return this list of 'K' elements.