Problem no 20: finding largest element in the array which is less than x.
QUESTION:
Given a sorted array arr[] of size N without duplicates, and given a value x. Floor of x is defined as the largest element K in arr[] such that K is smaller than or equal to x. Find the index of K(0-based indexing).
Example 1:
Input:
N = 7, x = 0
arr[] = {1,2,8,10,11,12,19}
Output: -1
Explanation: No element less
than 0 is found. So output
is "-1".
Example 2:
Input:
N = 7, x = 5
arr[] = {1,2,8,10,11,12,19}
Output: 1
Explanation: Largest Number less than 5 is
2 (i.e K = 2), whose index is 1(0-based
indexing).
ANSWER:
int findFloor(vector<long long> v, long long n, long long x)
{
long long max=INT_MIN;
long long index;
int singleelementpresentlessthanx=0;
for(long long i=0;i<n;i++)
{
if(v[i]<=x)
{
singleelementpresentlessthanx=1;
if(v[i]>max)
{
max=v[i];
index=i;
}
}
}
if(singleelementpresentlessthanx==0)
{
return -1;
}
else
{
return index;
}
}
Comments
Post a Comment