Home » Interview coding problems/challenges

# Floor and Ceil Value

**Floor and Ceil Value**: Given a sorted array of integers, find the floor and ceil of given number x in it. The floor and ceil value of a number points to the largest previous or the smallest following integer respectively.

Submitted by Divyansh Jaipuriyar, on August 20, 2020

**Problem statement:**

Given a sorted array of integers, find the floor and ceil of given number *x* in it. The floor and ceil value of a number points to the largest previous or the smallest following integer respectively.

**Problem description:**

The problem wants you to use the knowledge of mathematics as the floor is the value which is the largest integer less than or equal to *x* and ceil value is the smallest greater than or equal to *x*. We are required to approach the problem in a way such that the time complexity should change to linear to logarithmic.

**Input:**

The first line of the input is the *T* number of test cases. Each test case consists of integer *n* and *x*, size of the array, and the element whose floor and ceil value is to be evaluated respectively. Then each of the following lines contains n elements.

**Output:**

Print the floor and ceil value of the element *x*.

**Examples:**

Input: T=1 N=5,X=3 1,2,4,5,6 Output: floor: 2 ceil: 4

**Solution approach:**

**(a) Brute Force Approach:**

In this approach we will iterate through the array and simply find the floor and ceil of the element *x* in *O(n)* time.

The floor will the largest element smaller than or equal to element *x* and the ceil will be the smallest element greater than or equal to element *x*.

**Pseudo Code:**

For FLoor: //initialise some variable //floor with -1. floor=-1 //iteratively move through all //element until some largest element //greater than equal to x for i in length(arr[]): if(arr[i]<=x) floor=arr[i]//if found some element then assign. if(arr[i]>x)//if arr[i]>x then break. break For Ceil: //initialise some variable //ceil with -1. ceil=-1 //iteratively move through all //elements until smallest element //greater than equal to x. for i in length(arr[]): if(arr[i]>=x) ceil=arr[i],break

**Time Complexity** for the above approach in the worst case is: **O(n)**

**Space Complexity** for the above approach in the worst case is: **O(1)**

**b) Binary Search Approach:**

In this approach, we will use the concept of binary search to solve the problem. We will find the mid and then recur for the left or right side of the mid index according to the comparison.

**Pseudo Code:**

FOR CEIL: start and end are the range end points. //initialise ceil with -1. ceil=-1 CEIL(arr[],start,end): -> if x is equal to mid element then return mid element. -> if x is less than the mid element then ceil of the element x lies in left half of the range i.e in arr[start,mid], so we will change our celi value to mid element and search in left half arr[start,mid-1]. -> if x is greater than the mid element then ceil of the element x lies in the right half of the range i.e in arr[mid+1,end]. FOR FLOOR: start and end are the range end points. //initialise floor with -1. floor=-1 FLOOR(arr[],start,end): -> if x is equal to mid element then return mid element -> if x is less than mid element then floor lies in the left half of the range i.e arr[start,mid] -> if x is greater than the mid element then floor lies in the right half of the range i.e arr[mid,end],assign floor equal to mid. The floor lies in arr[mid+1,end] half.

**Time Complexity** for the above approach in the worst case is: **O(log(n))**

**Space Complexity** for the above approach in the worst case is: **O(1)**

**C++ Implementation (Brute Force Approach):**

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll t; cout << "Enter number of test cases: "; cin >> t; while (t--) { ll n, x; cout << "Enter N and X: "; cin >> n >> x; ll arr[n]; cout << "Enter array elements: "; for (ll i = 0; i < n; i++) cin >> arr[i]; ll ceil, floor; ceil = -1; floor = -1; //iterate through all elements //find largest element smaller than //equal to x. for (ll i = 0; i < n; i++) { if (arr[i] <= x) { floor = arr[i]; } else //if element found then break. break; } //iterate through all elements //find smallest element greater than //equal to x. for (ll i = 0; i < n; i++) { if (arr[i] >= x) { ceil = arr[i]; break; //break since we no need to //find any more element as //array is sorted. } } cout << "Floor:" << floor << " "; cout << "Ceil:" << ceil << "\n"; } return 0; }

**Output:**

Enter number of test cases: 3 Enter N and X: 5 3 Enter array elements: 1 2 3 4 5 Floor:3 Ceil:3 Enter N and X: 6 2 Enter array elements: 1 3 3 4 5 6 Floor:1 Ceil:3 Enter N and X: 4 7 Enter array elements: 3 6 8 8 Floor:6 Ceil:8

**C++ Implementation (Binary Search Approach):**

#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll t; cout << "Enter number of test cases: "; cin >> t; while (t--) { ll n, x; cout << "Enter N and X: "; cin >> n >> x; ll arr[n]; cout << "Enter array elements: "; for (ll i = 0; i < n; i++) cin >> arr[i]; ll ceil, floor; //initialize floor and ceil with -1. ceil = -1; floor = -1; //start index for binary search. ll l = 0; //end index for binary search. ll r = n - 1; //perform binary search. while (l <= r) { //mid index. ll mid = l + (r - l) / 2; //if found then assign and break. if (arr[mid] == x) { floor = arr[mid]; break; } //if x< mid element then search //left half range arr[l,mid-1]. if (arr[mid] > x) { r = mid - 1; } //if x> mid element then search //right half range arr[mid+1,r]. if (x > arr[mid]) { //since we are findin floor we need //to update the left floor each time. floor = arr[mid]; l = mid + 1; } } //reinitialise. l = 0; r = n - 1; //perform binary search again. while (l <= r) { //mid index. ll mid = l + (r - l) / 2; //if mid element equal to x //then break from loop. if (arr[mid] == x) { //assign ceil. ceil = arr[mid]; break; } //if x<arr[mid] then search in left //half range [l,mid-1] if (arr[mid] > x) { //assign each time ceil value as //search space is reducing. ceil = arr[mid]; r = mid - 1; } if (arr[mid] < x) { l = mid + 1; } } cout << "Floor:" << floor << " "; cout << "Ceil:" << ceil << "\n"; } return 0; }

**Output:**

Enter number of test cases: 3 Enter N and X: 5 3 Enter array elements: 1 4 6 8 9 Floor:1 Ceil:4 Enter N and X: 6 2 Enter array elements: 1 3 4 5 6 7 Floor:1 Ceil:3 Enter N and X: 3 2 Enter array elements: 3 5 7 Floor:-1 Ceil:3

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.