Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 17 Mar, 2021

Moderate

```
An integer 'a' is closer to 'X' than an integer 'b' if:
|a - X| < |b - X| or ( |a - X| == |b - X| and a < b )
```

```
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.
```

```
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'.
```

```
Return the k space-separated integers.
The output of each test case is printed on a new line.
```

```
1 <= T <= 5
1 <= N, K <= 5000
1 <= A[i], X <=10^6
Time Limit: 1 second
```

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.

The key idea is that we know that the final answer will be some contiguous sequence in array ‘A’. So we initially take the complete array as our answer then reduce its range.

Algorithm:

- Initially let ‘low' = 0 and ‘high’ = N - 1, Where ‘low’ and ‘high’ tell the range of integers taken in the final answer.
- If at any point (high - low + 1) = K, i.e., the size of the range is ‘K’, that range of integers is the answer. And we create a new array of that range and return it.
- If not, then we check if which one of ‘A[low]’ and ‘A[high]’ is at a smaller distance from ‘X’, whoever is at a smaller distance we keep it, and remove the other.
- If ‘low’ is at a smaller distance, we decrement ‘high’, i.e., high = high - 1.
- If ‘high’ is at a smaller distance, we increment ‘low’, i.e., low = low + 1.

Similar problems

Ninja And The Strictly Increasing Array

Moderate

Posted: 27 Nov, 2022

Negative To The End

Easy

Posted: 16 Dec, 2022

Sort 0s, 1s, 2s

Easy

Posted: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Posted: 24 Dec, 2022

Find Duplicate in Array

Easy

Posted: 5 Jun, 2023