Memorise array and print number of occurrences

Question

I have written a slow solution to the Memorise Me problem on hackerearth

The first line of input will contain N, an integer, which is the total number of numbers shown to your team.

The second line of input contains N space separated integers.

The third line of input contains an integer Q, denoting the total number of integers.

The Next Q lines will contain an integer denoting an integer, B_i, for which you have to print the number of occurrences of that number (B_i) in those N numbers on a new line.

If the number B_i isn’t present then print NOT PRESENT on a new line.

Constraints

$$1 \le N \le 10^5$$

$$0 \le B_i \le 1000$$

$$1 \le Q \le 10^{55}$$

    #include <stdio.h>
    int check(int z,int c[1001][2],int q,int arr[])
    {
        int i =0;
        while(c[i][0]!=-1)
        {
        if (z==c[i][0])
        {
            return c[i][1];
            break;
        }
    else
    {
        c[i][0]=z;
        c[i][1]=count(z,arr,q);
        return c[i][1];
    }
    i++;
    }

    }
     int count(int z,int arr[],int q)
     {
         int occurence=0;
         for(int k=0;k<q;k++)
         {
             if(z==arr[k])
             {
                 occurence++;
             }
         }
     return occurence;

     }
    int main()
    {
        int c[1001][2];

            for(int i=0;i<=1001;i++)
            {
                c[i][0]=-1;
                c[i][1]=0;
            }
            c[0][0]=9999;
        int n;
        scanf("%d",&n);
        int arr[100000];
        int i;
        for(i=0;i<n;i++){
            scanf("%d",&arr[i]);
            }
        int q;
        scanf("%d",&q);
        int j;
        int B[100000];
        int occurence1=0;

        for(j=0;j<q;j++)
        {
            scanf("%d",&B[j]);
            occurence1=check(B[j],c,q,arr);

            if(occurence1==0)
            {
                printf("NOT PRESENT\n");
            }
            else
            {
                printf("%d\n",occurence1);
            }
            }
        }

Code taking 0.9 seconds for a set of input where \$n=10^5\$ else it's taking 0.1 seconds. Can you suggest a shorter way to reduce time complexity! And suggest improvements in the code itself.

Answer 1

One of the things that's terrible about these types of competitions is that the problems are very contrived. They're written like a math problem, which makes it tempting to write your solutions the same way. I'd do the following things to improve your code.

Formatting

The formatting of your code is very messy. Maybe it's just due to getting used to entering code in the Stack Exchange text field, but even if the tabs were correct, you're not using a lot of white space between statements. I recommend looking at other people's code to see how they use whitespace and adopting a style that you like. The book Code Complete has some useful rules of thumb to use for how to style C code. It's a good place to start from.

Naming

This is the number one thing that most developers could improve (myself included!). Just because the problem description names things like N, Q, and B[i] doesn't mean your code has to use those names. You should strive to use readable names like numEntries, numQueries, and queries.

Your function names aren't great either. check() doesn't tell me what it's doing. What is it checking? It turns out nothing. It's tabulating the number of times z occurs in arr and putting the result into c. It might be better to name it something like tabulateEntries() or something along those lines. Likewise, count() is counting something, right? What is it counting? The number of occurrences of z. So maybe it should be named countOccurences()?

Be Careful With The Stack

You're allocating everything on the stack. This can get you in trouble with longer programs. For example, your declaration of B is using either 400 or 800KB of stack space. The default stack size in many implementations is 1MB, so this would use almost 80% of the stack just in your main() function. It might be wiser to allocate that space on the heap or better yet, only allocate as much as you actually need (which will be q elements instead of 100,000). Same thing with arr.

Avoid Magic Numbers

You have several magic numbers in your code. These are numbers that are hard-coded to specific values. Someone reading your code would have no idea where they come from. You should use named constants or enumerations where appropriate. For example,

const int kMaxQueries = 1000;
const int kUnsetEntry = -1;
const int kInvalidEntry = 9999;

Use structs Where Appropriate

You're using a 2 dimensional array to represent the values and their counts. You should instead use a struct that holds those 2 values and have a 1-dimensional array of those structs. Something like this:

typedef struct ValueCounts {
    int value;
    int count;
} ValueCounts;

Then you can write self-documenting code like this:

int check(int z, ValueCounts counts, int q, int arr[])
{
    int i = 0;
    while (counts[i].value != kUnsetEntry)
    {
        if (z == counts [ i ].value)
        {
            return counts [ i ].count;
        }
        else
        {
            counts [ i ].value = z;
            counts [ i ].count = count(z, arr, q);
            return counts [ i ].count;
        }
        i++;
    }
}

Errors

Notice that your check() function can return an undefined value. If c[i][0] == -1, then the while loop ends, and the function will return whatever's on the stack, which is likely uninitialized memory. Is this why you made c[0][0] have an initial value of 9999? While that works around the problem, it's a bad way to do it.

Performance

Looking at your code, it seems to be doing things the long way. arr is an unsorted array. Tabulating how many occurrences there are of a single value in arr potentially involves looping over the entirety of c processed so far. This can happen for every value in arr. It would probably be faster to sort arr before counting the occurrences of each value. If it were already sorted, you'd be able to just run through arr in order, and as soon as the value changed, you'd fill in the next value in c with the total number of occurrences of the value before the change. That would leave c in order and would allow you to do a binary search of c for getting the values needed to print out the result. That should be considerably faster than the linear search you're currently doing.

In fact, I went to the site and tried the above suggestions and passed the tests in the time allotted. For the sorting, I used the standard library qsort() function. I wrote my own binary search, and it seemed to do the trick.