How to solve in optimized time?

1
2

Are you out of your mind ?, you have created 3 posts for three different problem without giving any sort of explanation of the approraches you tried? STOP SPAMMING THRE FORUM

3

Plz reply politely if u know. Don’t get freaked.Stop giving lessons .If you know gently reply. I’m not forcing you to reply. And stop behaving like an idiot.

4

What wrong did he say? Creating three different random threads at same time without any context is spamming.

5

I guess you are supposed to use two pointers. First, sort the Array A in non decreasing order. Then, create an array of tuples, (value,index) for every element in B. Then sort the array based on value. Now, initialise two pointers i,j = 0,0; where i runs from 0 to length(A), and j runs from 0 to length(B). Now, for each j, increment i until A[i]<=B[j], and after condition fails, note the index i and increment j.

2 Likes
6 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
typedef struct tuple
{
    int value;
    int index;
    int count;
}tuple;
int ascending(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}
int sort_based_on_value(const void *a, const void *b)
{
    tuple *x, *y;
    x = (tuple *)a;
    y = (tuple *)b;
    return x->value-y->value;
}
int sort_based_on_index(const void *a, const void *b)
{
    tuple *x, *y;
    x = (tuple *)a;
    y = (tuple *)b;
    return x->index-y->index;
}
int main()
{
    int n;
    scanf("%d",&n);
    int *a = (int *)malloc(sizeof(int)*n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    qsort(a,n,sizeof(int),ascending);
    int m;
    scanf("%d",&m);
    tuple * b = (tuple *)malloc(sizeof(tuple)*m);
    for(int i=0;i<m;i++)
    {
        scanf("%d",&b[i].value);
        b[i].index = i;
    }
    qsort(b,m,sizeof(tuple),sort_based_on_value);
    int i=0;
    for(int j=0;j<m;j++)
    {
        while(i<n && a[i]<=b[j].value)
            i++;
        b[j].count = i;
    }
    qsort(b,m,sizeof(tuple),sort_based_on_index);
    for(int j=0;j<m;j++)
        printf("%d\n",b[j].count);
    return 0;
}

Here’s an O(M+N) solution.
Edit: The Time Complexity is O(max(m,n) * log(max(m,n))).

1 Like
7

Thanks:)

8

And you better follow the norms and maintain the decorum of the forum.

9

Yes I will , but mind your words.

10

Well, what wrong did I say anyways, even the moderator himself is backing my words