Tasks Details
easy
1.
Dominator
Find an index of an array such that its value occurs at more than half of indices in the array.
Task Score
75%
Correctness
62%
Performance
100%
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] = 3The 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
class Solution { public int solution(int[] A); }
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] = 3the 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].
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C#
Time spent on task 17 minutes
Notes
not defined yet
Task timeline
Code: 06:40:14 UTC,
cs,
verify,
result: Failed
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var size = 0;
var value = A[0] ;
for(int i=0; i<A.Length; i++)
{
if (size == 0)
{
size+=1;
value=A[i];
}
if (value != A[i])
{
size -=1;
}
}
var result = -1;
var candidate = value;
var count =0;
if (size!=0)
{
for(int i=0; i<A.Length; i++)
{
if (A[i]==candidate)
count++
}
if (count > A.Length/2)
result = candidate;
}
return result;
}
}
Analysis
Compile error
Compilation failed: 1 error(s), 0 warnings Solution.cs(36,13): error CS1002: ; expected
Code: 06:40:21 UTC,
cs,
verify,
result: Failed
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var size = 0;
var value = A[0] ;
for(int i=0; i<A.Length; i++)
{
if (size == 0)
{
size+=1;
value=A[i];
}
if (value != A[i])
{
size -=1;
}
}
var result = -1;
var candidate = value;
var count =0;
if (size!=0)
{
for(int i=0; i<A.Length; i++)
{
if (A[i]==candidate)
count++;
}
if (count > A.Length/2)
result = candidate;
}
return result;
}
}
Analysis
expand all
Example tests
example
example test
example test
✘
WRONG ANSWER
got 3, but element is not a dominator, value 2 has only 1 occurences (n=8)
got 3, but element is not a dominator, value 2 has only 1 occurences (n=8)
1.
0.061 s
WRONG ANSWER,
got 3, but element is not a dominator, value 2 has only 1 occurences (n=8)
Code: 06:43:06 UTC,
cs,
verify,
result: Failed
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var size = 0;
var value = A[0] ;
for(int i=0; i<A.Length; i++)
{
if (size == 0)
{
size+=1;
value=A[i];
}
if (value != A[i])
{
size -=1;
}
}
var result = -1;
List<int> pos = new List<int>();
var candidate = value;
var count =0;
if (size!=0)
{
for(int i=0; i<A.Length; i++)
{
if (A[i]==candidate)
{
count++;
pos.Add(i);
}
}
if (count > A.Length/2)
result = pos;
}
return result;
}
}
Analysis
Compile error
Compilation failed: 3 error(s), 0 warnings Solution.cs(27,9): error CS0246: The type or namespace name `List' could not be found. Are you missing `System.Collections.Generic' using directive? Solution.cs(38,21): error CS0841: A local variable `pos' cannot be used before it is declared Solution.cs(43,26): error CS0841: A local variable `pos' cannot be used before it is declared
Code: 06:43:38 UTC,
cs,
verify,
result: Failed
using System;
using System.Collections;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var size = 0;
var value = A[0] ;
for(int i=0; i<A.Length; i++)
{
if (size == 0)
{
size+=1;
value=A[i];
}
if (value != A[i])
{
size -=1;
}
}
var result = -1;
List<int> pos = new List<int>();
var candidate = value;
var count =0;
if (size!=0)
{
for(int i=0; i<A.Length; i++)
{
if (A[i]==candidate)
{
count++;
pos.Add(i);
}
}
if (count > A.Length/2)
result = pos;
}
return result;
}
}
Analysis
Compile error
Compilation failed: 3 error(s), 0 warnings Solution.cs(28,9): error CS0246: The type or namespace name `List' could not be found. Are you missing `System.Collections.Generic' using directive? Solution.cs(39,21): error CS0841: A local variable `pos' cannot be used before it is declared Solution.cs(44,26): error CS0841: A local variable `pos' cannot be used before it is declared
Code: 06:43:54 UTC,
cs,
verify,
result: Failed
using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var size = 0;
var value = A[0] ;
for(int i=0; i<A.Length; i++)
{
if (size == 0)
{
size+=1;
value=A[i];
}
if (value != A[i])
{
size -=1;
}
}
var result = -1;
List<int> pos = new List<int>();
var candidate = value;
var count =0;
if (size!=0)
{
for(int i=0; i<A.Length; i++)
{
if (A[i]==candidate)
{
count++;
pos.Add(i);
}
}
if (count > A.Length/2)
result = pos;
}
return result;
}
}
Analysis
Compile error
Compilation failed: 1 error(s), 0 warnings Solution.cs(44,26): error CS0029: Cannot implicitly convert type `System.Collections.Generic.List<int>' to `int'
Code: 06:45:07 UTC,
cs,
verify,
result: Failed
using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var size = 0;
var value = A[0] ;
for(int i=0; i<A.Length; i++)
{
if (size == 0)
{
size+=1;
value=A[i];
}
if (value != A[i])
{
size -=1;
}
}
var result = -1;
List<int> pos = new List<int>();
var candidate = value;
var count =0;
if (size!=0)
{
for(int i=0; i<A.Length; i++)
{
if (A[i]==candidate)
{
count++;
pos.Add(i);
}
}
}
if (count > A.Length/2)
return pos;
else
return -1;
}
}
Analysis
Compile error
Compilation failed: 1 error(s), 0 warnings Solution.cs(44,20): error CS0029: Cannot implicitly convert type `System.Collections.Generic.List<int>' to `int'
Code: 06:46:17 UTC,
cs,
verify,
result: Passed
using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var size = 0;
var value = A[0] ;
for(int i=0; i<A.Length; i++)
{
if (size == 0)
{
size+=1;
value=A[i];
}
if (value != A[i])
{
size -=1;
}
}
var result = -1;
List<int> pos = new List<int>();
var candidate = value;
var count =0;
if (size!=0)
{
for(int i=0; i<A.Length; i++)
{
if (A[i]==candidate)
{
count++;
pos.Add(i);
}
}
}
if (count > A.Length/2)
return pos[0];
else
return -1;
}
}
Analysis
Code: 06:46:26 UTC,
cs,
verify,
result: Passed
using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var size = 0;
var value = A[0] ;
for(int i=0; i<A.Length; i++)
{
if (size == 0)
{
size+=1;
value=A[i];
}
if (value != A[i])
{
size -=1;
}
}
var result = -1;
List<int> pos = new List<int>();
var candidate = value;
var count =0;
if (size!=0)
{
for(int i=0; i<A.Length; i++)
{
if (A[i]==candidate)
{
count++;
pos.Add(i);
}
}
}
if (count > A.Length/2)
return pos[0];
else
return -1;
}
}
Analysis
Code: 06:46:29 UTC,
cs,
final,
score:
75
using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can use Console.WriteLine for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
var size = 0;
var value = A[0] ;
for(int i=0; i<A.Length; i++)
{
if (size == 0)
{
size+=1;
value=A[i];
}
if (value != A[i])
{
size -=1;
}
}
var result = -1;
List<int> pos = new List<int>();
var candidate = value;
var count =0;
if (size!=0)
{
for(int i=0; i<A.Length; i++)
{
if (A[i]==candidate)
{
count++;
pos.Add(i);
}
}
}
if (count > A.Length/2)
return pos[0];
else
return -1;
}
}Analysis summary
The following issues have been detected: wrong answers, runtime errors.
Analysis
expand all
Correctness tests
1.
0.062 s
OK
2.
0.062 s
OK
1.
0.062 s
OK
2.
0.062 s
OK
1.
0.061 s
OK
2.
0.061 s
WRONG ANSWER,
got -1, but dominator exists, for example on position 8
1.
0.061 s
OK
extreme_empty_and_single_item
empty and single element arrays
empty and single element arrays
✘
RUNTIME ERROR
tested program terminated unexpectedly
tested program terminated unexpectedly
1.
0.056 s
RUNTIME ERROR,
tested program terminated unexpectedly
stderr:
Unhandled Exception: System.IndexOutOfRangeException: Array index is out of range. at Solution.solution (System.Int32[] A) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0 [ERROR] FATAL UNHANDLED EXCEPTION: System.IndexOutOfRangeException: Array index is out of range. at Solution.solution (System.Int32[] A) [0x00000] in <filename unknown>:0 at SolutionWrapper.run (System.String input, System.String output) [0x00000] in <filename unknown>:0 at SolutionWrapper.Main (System.String[] args) [0x00000] in <filename unknown>:0
2.
0.061 s
OK
1.
0.061 s
OK
2.
0.061 s
OK
1.
0.060 s
OK
2.
0.061 s
OK
extreme_half3
array with exactly ceil(N/2) values 1 + [0,0,1,1,1]
array with exactly ceil(N/2) values 1 + [0,0,1,1,1]
✘
WRONG ANSWER
got -1, but dominator exists, for example on position 1
got -1, but dominator exists, for example on position 1
1.
0.062 s
WRONG ANSWER,
got -1, but dominator exists, for example on position 1
2.
0.061 s
OK