Counting elements in two arrays
PROBLEM :
Given two unsorted arrays arr1[] and arr2[]. They may contain duplicates. For each element in arr1[] count elements less than or equal to it in array arr2[].
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains two integers m and n denoting the size of the two arrays. The following two lines will contain both the arrays respectively.
Output:
Print the count of elements less than or equal to it in arr2 for each element in arr1.
Constraints:
1<=T<=10^5
1<=m,n<=10^5
1<=arr1[i],arr2[j]<=10^5
Example:
Input:
2
6 6
1 2 3 4 7 9
0 1 2 1 1 4
5 7
4 8 7 5 1
4 48 3 0 1 1 5
Output:
4 5 5 6 6 6
5 6 6 6 3
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
// function to count for each element in 1st array,
// elements less than or equal to it in 2nd array
void countEleLessThanOrEqual(int arr1[], int arr2[], int m, int n)
{
sort(arr2,arr2+n) ;
for(int i=0;i<m;i++)
{
int start,end,mid ;
start=0 ;
end=n-1 ;
while(start<=end)
{
int mid=(start+end)/2 ;
if(arr2[mid]<=arr1[i])
start=mid+1 ;
else
end=mid-1 ;
}
cout<<end+1<<" " ;
}
}
--------------------------------------------------------------------------------
Given two unsorted arrays arr1[] and arr2[]. They may contain duplicates. For each element in arr1[] count elements less than or equal to it in array arr2[].
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains two integers m and n denoting the size of the two arrays. The following two lines will contain both the arrays respectively.
Output:
Print the count of elements less than or equal to it in arr2 for each element in arr1.
Constraints:
1<=T<=10^5
1<=m,n<=10^5
1<=arr1[i],arr2[j]<=10^5
Example:
Input:
2
6 6
1 2 3 4 7 9
0 1 2 1 1 4
5 7
4 8 7 5 1
4 48 3 0 1 1 5
Output:
4 5 5 6 6 6
5 6 6 6 3
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
// function to count for each element in 1st array,
// elements less than or equal to it in 2nd array
void countEleLessThanOrEqual(int arr1[], int arr2[], int m, int n)
{
sort(arr2,arr2+n) ;
for(int i=0;i<m;i++)
{
int start,end,mid ;
start=0 ;
end=n-1 ;
while(start<=end)
{
int mid=(start+end)/2 ;
if(arr2[mid]<=arr1[i])
start=mid+1 ;
else
end=mid-1 ;
}
cout<<end+1<<" " ;
}
}
--------------------------------------------------------------------------------
Comments
Post a Comment