Problem no 20: finding largest element in the array which is less than x.

 QUESTION:

 

Floor in a Sorted Array


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

Popular posts from this blog

problem 3: given two integers N and M. The problem is to find the number closest to N and divisible by M. If there are more than one such number, then output the one having maximum absolute value.

problem no 7:Given two numbers A and B, find Kth digit from right of AB.

Problem no 16: count the number of squares below N.