Dominator at app.codility.com/programmers in C Explained: Find an index of an array such that its value occurs at more than half of indices in the array.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N*log(N)) or O(N)
Lesson 8 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 5 Jul 2025
Problem
An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.For example, consider array A such that
A[0] = 3 A[1] = 4 A[2] = 3
A[3] = 2 A[4] = 3 A[5] = -1
A[6] = 3 A[7] = 3
The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.
Write a function
int solution(int A[], int N);
that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return -1 if array A does not have a dominator.
For example, given array A such that
A[0] = 3 A[1] = 4 A[2] = 3
A[3] = 2 A[4] = 3 A[5] = -1
A[6] = 3 A[7] = 3
the function may return 0, 2, 4, 6 or 7, as explained above.
Write an efficient algorithm for the following assumptions:
• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Strategy:
The lesson for this problem is on leader. Here, dominator means leader. However, it is any index for the leader that is required and not the leader itself. So the index of the last element in the stack, might be what is required. The last element is the candidate. If the candidate is a leader (dominator), its index should be returned. Otherwise there is no leader and -1 should be returned. If the stack ends up to be empty, then there is no leader and no corresponding index, and -1 should be returned.The reader is advised to read the lesson (tutorial) for this task (problem) if he/she has not already done so. The solution function is done in the same way that the O(n+n) algorithm was carried out in the lesson. However, here, the index of the possible last element in the stack should be noted.
Smart Solution
A program with the solution function is as follows (read through the code and comments). Pay particular attention to the solution() function definition and to the user code in the main() function.#include <stdio.h>The output is 7, which is one of the expected indexes.
#include <stdlib.h>
struct Element {
int value;
struct Element *previous;
};
struct Stack {
int size;
struct Element *back;
int (*top)();
void (*push)(int);
void (*pop)();
} stack;
int top() {
if (stack.size > 0) //stack has at least 1 element
return stack.back->value; //use -> to obtain value from a pointer
else
printf("Error: No element to remove from stack!\n");
}
void push(int inte) {
struct Element *element = malloc(sizeof(struct Element)); //declaring and creating the object, element
if (element != 0) { //check whether allocation of memory element was successful
element->value = inte;
if (stack.size == 0) { //first element
element->previous = 0;
stack.back = element;
stack.size = stack.size + 1; //add 1 to size
}
else {
element->previous = stack.back; //previous points to previous element
stack.back = element; //stack points to new element
stack.size = stack.size + 1; //add 1 to size
}
}
else {
printf("Error: New element could not be created!\n");
exit(1);
}
}
void pop() {
if (stack.size > 0) { //stack has at least 1 element
struct Element *lastElement = stack.back;
stack.back = lastElement->previous; //point to previous element
free(lastElement); //free last (top) element from memory
stack.size = stack.size - 1; //subtract 1 from size
}
else {
printf("Error: No element to remove from stack!\n");
exit(1);
}
}
int solution(int A[], int N) {
int dominator = -2147483648;
stack.push(A[0]);
// O(n) time
for (int i=1; i<N; i++) {
if (stack.size != 0 && stack.top() == A[i])
stack.push(A[i]);
else if (stack.size != 0) //stack top and in-coming are different
stack.pop();
else //stack is empty
stack.push(A[i]);
}
int candidate = -1;
if (stack.size != 0)
candidate = stack.top();
else
dominator = -2147483648;
int indx = -1;
int count = 0;
// Another O(n) time
for (int i=0; i<N; i++) {
if (A[i] == candidate) {
count += 1;
indx = i;
}
}
if (count > N/2)
return indx;
else
return -1;
}
int main(int argc, char **argv)
{
//Assigning stack attributes and methods (functions)
stack.size = 0;
stack.top = top;
stack.push = push;
stack.pop = pop;
//user code begins
int A[] = {3, 4, 3, 2, 3, -1, 3, 3};
int N = sizeof(A)/sizeof(A[0]); //divide size of array by size of one (first) element
int ret = solution(A, N);
printf("%i\n", ret);
//user code begins
return 0;
}
At app.codility.com/programmers the scoring and detected time complexity for this solution() is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N*log(N)) or O(N)