Test results - Codility

Tasks Details

easy

1. PermMissingElem

Find the missing element in a given permutation.

Task Score

100%

Correctness

100%

Performance

100%

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];

the elements of A are all distinct;

each element of array A is an integer within the range [1..(N + 1)].

Solution

Programming language used C#

Time spent on task 55 minutes

Notes

not defined yet

Code: 14:32:19 UTC, c, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");

int solution(int A[], int N) {
    // write your code in C99 (gcc 4.8.2)
    
    
    
    
    
    		int last = 0;
		System.Array.Sort (A);

		for(int i = 1; i < A.Length + 1; i++)
		{
			last = i;
			bool isFound = false;

			if(i == A[i - 1])
			{
				isFound = true;
				break;
			}

			if(!isFound) return i;
		}
		return last + 1;

    
    
    
    
    
}

Analysis

Compile error

func.c: In function 'solution':
func.c:12:3: error: 'System' undeclared (first use in this function)
   System.Array.Sort (A);
   ^
func.c:12:3: note: each undeclared identifier is reported only once for each function it appears in
func.c:14:23: error: request for member 'Length' in something not a structure or union
   for(int i = 1; i < A.Length + 1; i++)
                       ^
func.c:17:4: error: unknown type name 'bool'
    bool isFound = false;
    ^
func.c:17:19: error: 'false' undeclared (first use in this function)
    bool isFound = false;
                   ^
func.c:21:15: error: 'true' undeclared (first use in this function)
     isFound = true;
               ^

Code: 15:25:11 UTC, c, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");

int solution(int A[], int N) {
    // write your code in C99 (gcc 4.8.2)
		System.Array.Sort (A);

		int count = 0;

		for(int i = 0; i < A.Length; i++)
		{
			bool isFound = false;
			count = i + 1;
			Debug.Log ("A[i] : " + A[i] + " : count : " + count);

			if(A[i] == count)
			{
				isFound = true;
				Debug.Log ("isFound : true");
				continue;
			}

			Debug.Log ("isFound : " + isFound);
			if(!isFound) return count;
		}
		return count + 1;

}

Analysis

Compile error

func.c: In function 'solution':
func.c:6:3: error: 'System' undeclared (first use in this function)
   System.Array.Sort (A);
   ^
func.c:6:3: note: each undeclared identifier is reported only once for each function it appears in
func.c:10:23: error: request for member 'Length' in something not a structure or union
   for(int i = 0; i < A.Length; i++)
                       ^
func.c:12:4: error: unknown type name 'bool'
    bool isFound = false;
    ^
func.c:12:19: error: 'false' undeclared (first use in this function)
    bool isFound = false;
                   ^
func.c:14:4: error: 'Debug' undeclared (first use in this function)
    Debug.Log ("A[i] : " + A[i] + " : count : " + count);
    ^
func.c:14:32: error: invalid operands to binary + (have 'char *' and 'char *')
    Debug.Log ("A[i] : " + A[i] + " : count : " + count);
                                ^
func.c:18:15: error: 'true' undeclared (first use in this function)
     isFound = true;
               ^

Code: 15:25:22 UTC, c, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");

int solution(int A[], int N) {
    // write your code in C99 (gcc 4.8.2)
		System.Array.Sort (A);

		int count = 0;

		for(int i = 0; i < A.Length; i++)
		{
			bool isFound = false;
			count = i + 1;

			if(A[i] == count)
			{
				isFound = true;
				continue;
			}

			if(!isFound) return count;
		}
		return count + 1;

}

Analysis

Compile error

func.c: In function 'solution':
func.c:6:3: error: 'System' undeclared (first use in this function)
   System.Array.Sort (A);
   ^
func.c:6:3: note: each undeclared identifier is reported only once for each function it appears in
func.c:10:23: error: request for member 'Length' in something not a structure or union
   for(int i = 0; i < A.Length; i++)
                       ^
func.c:12:4: error: unknown type name 'bool'
    bool isFound = false;
    ^
func.c:12:19: error: 'false' undeclared (first use in this function)
    bool isFound = false;
                   ^
func.c:17:15: error: 'true' undeclared (first use in this function)
     isFound = true;
               ^

Code: 15:26:24 UTC, cs, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

using System;
// you can also use other imports, for example:
// using System.Collections.Generic;

// you can write to stdout 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)
        
        
        		System.Array.Sort (A);

		int count = 0;

		for(int i = 0; i < A.Length; i++)
		{
			bool isFound = false;
			count = i + 1;
			Debug.Log ("A[i] : " + A[i] + " : count : " + count);

			if(A[i] == count)
			{
				isFound = true;
				Debug.Log ("isFound : true");
				continue;
			}

			Debug.Log ("isFound : " + isFound);
			if(!isFound) return count;
		}
		return count + 1;

        
        
    }
}

Analysis

Compile error

Compilation failed: 3 error(s), 0 warnings
Solution.cs(21,4): error CS0103: The name `Debug' does not exist in the current context
Solution.cs(26,5): error CS0103: The name `Debug' does not exist in the current context
Solution.cs(30,4): error CS0103: The name `Debug' does not exist in the current context

Code: 15:26:47 UTC, cs, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

using System;

class Solution {
    public int solution(int[] A) {
        System.Array.Sort (A);

		int count = 0;

		for(int i = 0; i < A.Length; i++)
		{
			bool isFound = false;
			count = i + 1;

			if(A[i] == count)
			{
				isFound = true;
				continue;
			}

			if(!isFound) return count;
		}
		return count + 1;
    }
}

Analysis

expand all Example tests

▶

example
example test

✔

0.039 s

Code: 15:26:58 UTC, cs, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

using System;

class Solution {
    public int solution(int[] A) {
        System.Array.Sort (A);

		int count = 0;

		for(int i = 0; i < A.Length; i++)
		{
			bool isFound = false;
			count = i + 1;

			if(A[i] == count)
			{
				isFound = true;
				continue;
			}

			if(!isFound) return count;
		}
		return count + 1;
    }
}

Analysis

expand all Example tests

▶

example
example test

✔

0.059 s

Code: 15:27:00 UTC, cs, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

using System;

class Solution {
    public int solution(int[] A) {
        System.Array.Sort (A);

		int count = 0;

		for(int i = 0; i < A.Length; i++)
		{
			bool isFound = false;
			count = i + 1;

			if(A[i] == count)
			{
				isFound = true;
				continue;
			}

			if(!isFound) return count;
		}
		return count + 1;
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N) or O(N * log(N))

expand all Example tests

▶

example
example test

✔

0.069 s

expand all Correctness tests

▶

empty_and_single
empty list and single element

✔

0.069 s

▶

missing_first_or_last
the first or the last element is missing

✔

0.069 s

▶

single
single element

✔

0.069 s

0.065 s

▶

double
two elements

✔

0.069 s

0.068 s

0.069 s

▶

simple
simple test

✔

0.069 s

expand all Performance tests

▶

medium1
medium test, length = ~10,000

✔

0.071 s

▶

medium2
medium test, length = ~10,000

✔

0.074 s

▶

large_range
range sequence, length = ~100,000

✔

0.109 s

0.086 s

▶

large1
large test, length = ~100,000

✔

0.115 s

▶

large2
large test, length = ~100,000

✔

0.100 s