Counting elements in two arrays using C++

Let us assume that we have given two unsorted arrays arr1[] and arr2[]. The task is to count the total number of elements in arr2[] for which each element of arr1[] are less than or equal to the elements present in arr2[]. However, the element in both the array may contain duplicates too.

For example,

Input-1 −

N = 6 M = 7 arr1[N] = {1, 2, 5, 0, 6, 3} arr2[M] = {0,0,1,2,1,3,4,6,8}

Output −

4 5 7 2 8 6

The approach used to solve this problem

To count every element of arr1[] and check if they are less than or equal to the elements in arr2[], the idea is to sort arr2[] and use the binary search method to find the element of arr1[] which are less or equal to the element present in the arr2[].

• Take input the size of arr1 and arr1 as ‘m’ and ‘n’.

• Take input of the array elements.

• A function countInSecond(int *arr1, int *arr2, int m, int n) takes two arrays and its size as input and returns the count of the element present in the arr2[].

• Sort the arr2[].

• Iterate over the arr1[] and use binary search to find the particular element in the arr2[].

• Return the count of the element less than or equal.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; void countInSecond(int *nums1,int *nums2,int m,int n){    sort(nums2, nums2+n);    int i=0;    for(int i=0;i<m;i++){       int s=0;       int e=n-1;       while(s<=e){          int mid= (s+e)/2;          if(nums2[mid]<=nums1[i])             s= mid+1;          else             e= mid-1;       }       cout<<e+1<<" ";    } } int main(){    int m=6;    int n=9;    int arr1[m]={1,2,5,0,6,3};    int arr2[n]= {0,0,1,2,1,3,4,6,8};    countInSecond(arr1,arr2,m,n);    return 0; }

Output

Running the above code will generate the output as,

4 5 7 2 8 6

The count of all the elements of arr1 which are less than or equal to those in arr2 is {4 5 7 2 8 6}.