Question

Let A[1 · · · n] be an array of n elements and B[1 · · · m] an array of m elements. We assume that m ≤ n. Note that neither A nor B is sorted. The problem is to compute the number of elements of A that are smaller than B[i] for each element B[i] with 1 ≤ i ≤ m.

For example, let A be {30, 20, 100, 60, 90, 10, 40, 50, 80, 70} of ten elements. Let B be {60, 35, 73} of three elements. Then, your answer should be the following: for 60, return 5 (because there are 5 numbers in A smaller than 60); for 35, return 3; for 73, return 7.

(a) Design an O(mn) time algorithm for the problem. (10 points)

(b) Improve your algorithm to O(n log m) time. (20 points)
Hint: Use the divide and conquer technique. Since m ≤ n, you cannot sort the array A because that would take O(n log n) time, which is not O(n log m) as m may be much smaller than n.

Note: For this problem, you need to describe the main idea of your algorithms and briefly analyze their time complexities. You will receive the full 30 points if you give an O(n log m) time algorithm directly for (b) without giving any algorithm for (a).

Answer 1

#include<bits/stdc++.h>
using namespace std;

int main(){

    vector<int> A = {30, 20, 100, 60, 90, 10, 40, 50, 80, 70} ;
    vector<int> B = {60,35,73};

    sort(B.begin(),B.end());  // sort the B vector   time complexity O(m(logm))
    const int m = B.size(); 
    const int n = A.size(); 
    int fre[m+1];       // this will store the frequency of elements in A smaller than a elements in B
    memset(fre,0,sizeof(fre));


    /*
     * Algo :
     * for every element of A 
     *      find the element in B which is strictly less than that element
     *      and increase  the frequency of that index by one.
     *
     *
     *  At last take the cummlative sum of the frequency array to find the required ans
     */



    for(int i=0;i<n; i++){   // this is binary search in O(logm) time for one A's element 
        int low = 0;
        int high = m-1;
        int ans = -1;
        while(low <= high){
            int mid = low + (high - low)/2;
            if(B[mid] < A[i]){
                ans = mid;
                low = mid + 1;
            }
            else{
                high =mid  - 1;
            }
        }
        if(ans == -1){
            fre[0]++;
        }
        else{
            fre[ans+1]++;
        }
    }
    for(int i=1;i<=m;i++) fre[i] += fre[i-1];
    for(int i=0;i<m;i++){
        cout<<"No of values samller than "<<B[i]<<" are: "<<fre[i]<<endl;
    }
}