Last Updated: 1 Dec, 2021
Find Student
Easy
Asked in company
There are 'N' students standing in a line, and their heights are given. But the constraint is that the difference in heights of adjacent students does not exceed 'K', i.e.,
| height[i] - height[i+1] | <= K, where i ∈ (1, N-1)
Your task is to find the position of a student having height 'H'. If no such student is found, return -1.
Note:
Positions are counted starting from 0.
If two or more students have height equal to 'H', return the student with the minimum position.
Input Format:
The first line contains 'T', denoting the number of tests.
For each Test :
The first line contains three space-separated integers 'N', 'K' and 'H', denoting the number of students, the maximum difference in adjacent heights, and height of target student, respectively.
The second line contains an array 'A' of length 'N', denoting the heights of students.
Output Format:
For each test, print an integer, denoting the minimum position of a student having a height equal to 'H'.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints -
1 <= 'T' <= 5
1 <= 'N' <= 10^5
1 <= K, A[i] <= 10^9 i ∈ (1, N)
Note - Sum of 'N' over all test cases does not exceed 10^5.
Time Limit: 1 sec
Approaches
Approach: Run a linear search to find the desired height in an array of heights. If such a student is found, return its position immediately, else return -1.
Algorithm:
- Iterate a for loop, i = 0 to N-1.
- If A[i] is equal to 'H', return 'i'.
- Return -1.
Approach: We use the fact that adjacent elements have a maximum difference of value 'K'. Hence, at position 'i', if the difference of 'H' and A[i] is greater than 'K', it can be guaranteed that desired height 'H' is not available at position i+1.
Calculate the difference between 'H' and A[i] for each position, let it be 'diff'. Using the above observation, from position 'i', we can directly jump to i + (diff / K).
Algorithm:
- Start the iterator 'i' at position 0.
- While 'i' is less than N.
- If A[i] equals 'H', return 'i'.
- Calculate the steps that can be jumped, i.e., steps = abs(A[i] - H) / K.
- If 'steps' is less than 1, make it 1.
- i += steps.
- Return -1.
Similar problems