Last Updated: 31 Dec, 2020
Minimum Distance Between Two Numbers
Easy
Asked in company
You’re given an array of 'N' integers, and two integers 'X' and 'Y'. Your task is to find the minimum distance between 'X' and 'Y' in the array. If either or both of them are not present in the array then return -1.
NOTE :
1. The array might also contain duplicates.
2. It is guaranteed that 'X' and 'Y' are two distinct integers i.e. 'X' is not equal to 'Y'.
Input Format :
The first line contains an integer 'T', denoting the number of test cases.
The first line of each test case contains three space-separated integers 'N', 'X', 'Y', as described in the problem statement.
The second line of each test case contains 'N' space-separated integers, the elements of the array.
Output Format :
For each test case, print the minimum distance between 'X' and 'Y' and if any or both of them('X' and 'Y') are not present in the array then print -1.
Print the output of each test case in a separate line
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
0 <= X, Y <= 10^9
0 <= ARR[i] <= 10^9
Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array ‘ARR’ respectively, 'X' and 'Y' denotes the integer given in the input, and 'ARR[i]' denotes the 'i-th' element of the array 'ARR'.
Time Limit : 1 sec
Approaches
Approach: In this approach, we’ll use brute force. As we are supposed to find the minimum distance between the two integers, we’ll do this by using nested loops. The outer loop will be used for selecting the X(our first element) and the inner loop will be used for traversing the array in search for Y(another element) and taking the minimum distance between them. Let us understand how we will implement these steps.
- First, we’ll start by creating a variable minimunDist = INT_MAX
- Then we will run a nested loop, the outer loop runs from start to end (loop counter i), the inner loop runs from i+1 to end (loop counter j).
- If the ith element is X and the jth element is Y or vice versa, we will update m as minimunDist = min(minimunDist,j-i)
- Print the value of minimunDist as minimum distance.
In this efficient approach, we will check only consecutive pairs of X and Y. For every element X or Y, we will check the index of the previous occurrence of X or Y. If the previous occurring element is not similar to the current element, then we update the minimum distance.
But a question still arises, What if an X is preceded by another X and that is preceded by a Y? If this is so then how to get the minimum distance between pairs. But if we observe carefully, it can be seen that every X followed by a Y or vice versa can only be the closest pair (minimum distance) so ignore all other pairs. This will space a lot of our time.
Let us understand how we will implement these steps.
- First we’ll start by creating a variable minimunDist = INT_MAX and prev = -1
- We will then traverse the array from start to end.
- If the current element is X or Y and prev is not equal to -1 and at the same time if array[prev] is not equal to a current element then we will update m = max(current_index - prev, minimunDist), i.e. we will find the distance between consecutive pairs and we will also update m with it.
- We'll update the value of the prev variable and make it equal to the current value of the iterator whenever we encounter X or Y.
- If prev = -1, we’ll print -1 else we will print the value of m, which is our answer.
- For example- N= 7, X =2, Y = 4 and A[] = 1 2 3 4 2 3 5
- Initially, prev = -1 and our iterator will point to the 2nd position(The first occurrence of 2) and as of now our minimum distance is infinite(INT_MAX).
- Now we move further and now our iterator is at the fourth position(The first occurrence of 4) and prev = 2. Hence minimum distance as of now is 2(4th Position - 2nd Position).
- Moving further we have our iterator at the 5th position(The second occurrence of 2) and prev = 4. Now our distance between the new position of 2 and 4 is 1(5th position - 4th position ).
- As 1 < 2, we update our minimum distance to be 1.
- We then print 1, which is our answer.
Similar problems