1
\$\begingroup\$

My program has to read an array and say whether there is a predominant number or not in the array. A predominant number is the one with frequency bigger than number of elements of the array divided by 2. I did it, but the site I am learning on is dissatisfied with the program's speed so I do not have the maximum score. Not for that score I am asking this.

int main()
{
    int number, i, j, currentElAp = 1, maxAp = 0, maxApNumber = -1, remainingElements;
    scanf("%d", &number);
    int ar[number];
    for(i = 0; i < number; i++)
        scanf("%d", &ar[i]);

    for(i = 0; i < number / 2; i++){
        remainingElements = number - i - 1;
        if(ar[i] != maxApNumber){
            for(j = i + 1; j < number && (remainingElements + currentElAp > number / 2); j++){
                if(ar[i] == ar[j])
                    currentElAp++;
            }
        }
        if(currentElAp > maxAp){
            maxAp = currentElAp;
            maxApNumber = ar[i];
        }
        currentElAp = 1;
    }
    if(maxAp > number / 2)
        printf("Yes %d %d", maxApNumber, maxAp);
    else
        printf("No");
    return 0;
}

Restrictions:

  1. 1 ≤ number ≤ 100.000
  2. Each element of the array is smaller than 1.000.000.000

How could my code be improved to be faster or how would you write a faster solution?

\$\endgroup\$
  • 4
    \$\begingroup\$ Check out Boyer–Moore majority vote algorithm \$\endgroup\$ – vnp May 22 '17 at 16:04
  • \$\begingroup\$ In case you need a link to the above algorithm, here's the Wikipedia article on it. \$\endgroup\$ – user1118321 May 23 '17 at 3:13
  • \$\begingroup\$ Yes, I used Boyer-Moore algorithm and it is faster than my program even if I had to loop the array one more time to find if the return of this algorithm is truly a majority element. \$\endgroup\$ – Timʘtei May 23 '17 at 7:27
1
\$\begingroup\$

This is a very straightforward implementation and fairly easy to read. Nice work! Here are some ways it could be improved:

Performance

Since you asked about performance, let's start there. Looking at your inner loop, it looks like you are going through the entire array for every element of the array. (Actually, I think there's a mistake here. It looks like you intended to write for (j = i + 1... on the inner loop, but instead wrote for j = 1 + 1....)

Rather than doing it that way, what if we had the numbers already in order? Then it would be really easy to do, wouldn't it? You could just make 1 pass through the array, counting up the number of occurrences of each number as you go. Once you find the predominant one, you can skip the rest.

Furthermore, if at any point you have fewer than 1/2 + 1 numbers left and you switch to a new number, you automatically know that there is no predominant number. So you never have to traverse the entire array, unless the entire second half of the array contains the same number. So in the vast majority of cases you won't traverse the entire array.

So I would add a call to qsort() to sort the numbers after reading in the array. Then your remaining code would be significantly simplified, and would probably be significantly faster.

Naming

Your variable names could use some help. You're on the right track, but I would go further. Instead of number which is quite generic (everything's a number to the computer!), why not numEntries or numElements? i and j are fine for loop indexes.

What does Ap stand for? I see currentElAp, maxAp, etc. But I don't understand what it means. As such, I'd expand it to whatever it stands for.

Functions

I would break the program into separate functions with good names that describe what it does. For example, you could have a readEntries() function that reads in the array, a findPredominantNumber() function that finds the numbers you're looking for, and a displayResults() function that prints everything out. It would make the code more readable and easier to understand at a glance.

Stylistic Stuff

I would suggest a few stylistic improvements. In general it's best to put one variable declaration per line. It's easier to read and can avoid some common errors, like thinking that you're declaring a pointer when you're not.

Use more whitespace! I see only a single blank line in your function. It would be nice to see some more between the last for and the final if.

I would also recommend using brackets around single-line statements in an if or for body because this can also reduce the possibility of errors. This one is especially important on code that will be maintained over years.

\$\endgroup\$
  • \$\begingroup\$ Thanks! ap stands for appearances. I do not know how it sounds in english, but in my native language this is the common word. \$\endgroup\$ – Timʘtei May 23 '17 at 4:05
0
\$\begingroup\$

(This answer builds on the approach in user1118321's answer.)

Having sorted the input elements, we know that if there is a predominant element, the median value must be it. So we can work out from central element (perhaps using some variant of binary search) until we find two elements n/2 apart that are either both different to the median, or both the same. You'll want to be careful about whether that n/2 needs to be rounded up or down at each point.

Remember to implement some error handling for non-positive n!

\$\endgroup\$
  • 1
    \$\begingroup\$ While it's true that if the median equals the first or last element, it's the predominant element, but checking first and last probably isn't an optimization. Consider the sequence 1,3,3,3,5 in which the predominant entry (3) is equal to neither the first nor last element. \$\endgroup\$ – Edward May 23 '17 at 11:43
  • \$\begingroup\$ You're right - I've edited to make a different recommendation, based on identifying the median as the predominant element if one exists. \$\endgroup\$ – Toby Speight May 23 '17 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.