Ceil The Floor

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
486 upvotes
Asked in company
Royal Bank of Scotland

Problem statement

You're given a sorted array 'a' of 'n' integers and an integer 'x'.


Find the floor and ceiling of 'x' in 'a[0..n-1]'.


Note: 
Floor of 'x' is the largest element in the array which is smaller than or equal to 'x'.
Ceiling of 'x' is the smallest element in the array greater than or equal to 'x'.


Example: 
Input: 
n=6, x=5, a=[3, 4, 7, 8, 8, 10]   

Output:
4

Explanation:
The floor and ceiling of 'x' = 5 are 4 and 7, respectively.


Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two integers, ‘n’ and 'x', where n represents the size of the array.

The next line contains 'n' integers, denoting the elements of the given array.


Output Format : 
Return two integers, the floor and ceiling of 'x'.


Note : 
You are not required to print anything; it has already been handled. Just implement the function.
Sample Input 1 :
6 8
3 4 4 7 8 10


Sample Output 1 :
8 8


Explanation of sample input 1 :
Since x = 8 is present in the array, it will be both floor and ceiling.


Sample Input 2 :
6 2
3 4 4 7 8 10


Sample Output 2 :
-1 3


Explanation of sample input 2 :
Since no number is less than or equal to x = 2 in the array, its floor does not exist. The ceiling will be 3.


Constraints :
1 <= n <= 2 * 10^5      
1 <= a[i] <= 10^9
Time limit: 1 sec
Hint

Try iterating each element of the array!

Approaches (2)
Linear Search

Simply iterate all the elements of the array. While iterating, check each number for floor and ceil.


 

The steps are as follows:

  1. Initialize ‘FLOOR’ with -1 and ‘CEIL’ with positive infinity.
  2. Iterate the given array.
    • If ai >= X and ai < CEIL
      • CEIL = ai
    • If ai <= X and ai > FLOOR
      • FLOOR = ai
  3. If CEIL is still positive infinity:
    • CEIL = -1
  4. Return the pair of FLOOR and CEIL.

 

 

Time Complexity

O(N), where ‘N’ is the length of the array given.

 

We are iterating the entire array. Hence time complexity linearly depends on the size of the input array.

 

Space Complexity

O(1)

 

No auxiliary space used is dependent on the size of the input array.

Code Solution
(100% EXP penalty)
Ceil The Floor
Full screen
Console