Floor Value of X

Easy
0/40
Average time to solve is 15m
8 upvotes
Asked in companies
GrofersIncode

Problem statement

You are given a sorted array ‘A’ and an integer ‘X’. Your task is to find and return the floor value of ‘X’ in the array.

The floor value of ‘X’ in array ‘A’ is the largest element in the array which is smaller than or equal to X.

Note: In case there is no floor value of ’X’ in the array ‘A’, return -1.

For example:

For the given arr[  ] = { 1, 2, 5, 7, 12, 14 }  and X = 10

The floor of 10 is 7 because 7 is the largest element in the array which is smaller than 10.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘N’ denoting the number of elements in the array.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.

The third and the last line of each test case contains an integer representing ‘X’.
Output Format: 
For each test case, print a single integer ‘K’ denoting the floor value of ‘X’ in the array. In case, there is no floor value of ’X’ in the array ‘A’, print -1.

The output of each test case will be printed on a separate line.
Note: 
You do not need to input or print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N <= 5 * 10 ^ 4
0 <= X, A[i] <= 10 ^ 8

Time Limit: 1 sec.
Sample Input 1:
2
6
1 2 5 7 12 14
10
5
10 20 30 40 50
50
Sample Output 1:
7
50
Explanation of Sample Input 1:
In the first test case, the floor of 10 is 7, because 7 is the largest element in the array which is smaller than 10.

In the second test case, the floor of 50 is 50.
Sample Input 2:
1
4
4 8 9 11
3
Sample Output 2:
-1
Explanation of Sample Output 2:
In the first test case, the floor of 3 is -1, because 3 is smaller than all the elements in the array.
Hint

Compare each value of array.

Approaches (2)
Linear Search

The idea is to iterate from left to right of the array and compare ‘X’ with the elements of the array, while it is smaller than or equal to ‘X’ then update the answer else stop.

 

Algorithm :

 

Let the function be ‘floorSearch(‘A’, ‘X’, ‘N’)’, which returns the floor of ‘X’ in the array ‘A’ of length ‘N’.

 

  • If A[0] is greater than ‘X’ return -1
  • Take a variable ‘ans’, that stores the floor value of ‘X’.
  • Run a loop from 0 to ‘N’ - 1
    • If A[ i ] is less than or equal ‘X’
      • Update ‘ans’ = A[i]
    • Else
      • Break
  • Return ‘ans’.
Time Complexity

O(N),  where ‘N’ is the number of elements in a given array.

 

In the worst case, ‘X’ is greater than all the elements in the array. So, it compares from start till the end of the array. Hence time complexity is O(‘N’).

Space Complexity

 O(1)

 

We are using constant space.

Code Solution
(100% EXP penalty)
Floor Value of X
Full screen
Console