Last Updated: 4 Dec, 2020
Search For Integers With Given Difference And At Given Distance
Moderate
Asked in company
You are given an array consisting of 'N' non-negative integers, and two non-negative integers 'K' and 'M', your task is to find a pair of indices(say i and j) from the array such that ‘i’ ≠ ‘j’, |Ai-Aj| <= 'M', and |i-j| <= 'K', where |a-b| represents the absolute value of a-b.
Note :
1) The array may contain duplicate elements.
2) The size of the array is at least 2.
3) The given array follows 0-based indexing so 0 <= i,j< N.
4) It is guaranteed that there exist at least one such pair of indices.
Input Format :
The first line of the input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains three space-separated integers 'N', 'K', and 'M', as described in the problem statement.
The second line of each test case contains 'N' space-separated integers, representing the elements of the array.
Output Format :
You just need to find the pair of indices(i and j), and if the pair returned satisfies the given condition, the output will be shown as “valid”, else the output will be shown as “invalid”.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= N <= 10^4
1 <= K <= N
1 <= M <= 10^9
1 <= ARR[i] <= 10^9
Where 'ARR[i]' denotes the 'ith' element of the array.
Time Limit: 1 sec
Approaches
- Idea behind this brute force approach is to run nested loop and each time visit next k elements( because as per the problem statement the indices must have a difference of at most K) from the present index, until we find a pair that satisfies the given conditions.
- Now, run a loop(say, loop variable i) through all the elements of the array:
- Run a nested loop(say, loop variable j) through the elements starting from index i+1 upto next k elements(if present, else till the end of the array).
- At each iteration of the inner loop check if the absolute difference of the element at index i and that at index j is at most M then return the indices i and j as the answer, else continue with the process.
- Store all the array elements along with their indices in a vector of pairs (say, vector< pair <int,int> >v).
- Now, sort this vector in ascending order.
- Maintain two pointers i and j and initialize i to 0 and j to 1, and an empty set.
- Now run a loop until i<N and j<N, and if the difference of element at index j and at index i is less than M then insert index j into the set and increment j by 1. Otherwise do the following:
- Find the lower bound of index i in the set (lowerbound(i), is the smallest element in the set that is greater than or equal to the index i), before finding the lower bound erase the index i from the set, if present because we want pair of different indices not the same.
- If the absolute difference between the lower bound of index i and index i is at most K then return these indices and break out from the loop.
- If the absolute difference is greater than k, then we check for the upper bound of i in the set (upperbound(i), is the largest element that is smaller than or equal to i), and then we check for the absolute difference between the upper bound and i, and if it is at most k then return the pair as answer, and break out from the loop, otherwise continue with the process.
Similar problems