Test results - Codility

Tasks Details

easy

1. OddOccurrencesInArray

Find value that occurs in odd number of elements.

Task Score

66%

Correctness

100%

Performance

25%

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the elements at indexes 0 and 2 have value 9,

the elements at indexes 1 and 3 have value 3,

the elements at indexes 4 and 6 have value 9,

the element at index 5 has value 7 and is unpaired.

Write a function:

function solution($A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9

the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

N is an odd integer within the range [1..1,000,000];

each element of array A is an integer within the range [1..1,000,000,000];

all but one of the values in A occur an even number of times.

Solution

Programming language used PHP

Time spent on task 7 minutes

Notes

not defined yet

Task timeline

Code: 16:29:22 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
    }
}

Code: 16:29:26 UTC, php, autosave

show code in pop-up

1 2 3 4 5 6

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

function solution($A) {
    // write your code in PHP7.0
}

Code: 16:29:32 UTC, php, autosave

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        for ($j = $N-1 ; $j > $i ; $j--) {
            if ($A[$i] == $A[$j]) {
                $A[$i] = null;
                $A[$j] = null;
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:30:24 UTC, php, autosave

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.
// print "this is a debug message\n";

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        
        for ($j = $N-1 ; $j > $i ; $j--) {
            if ($A[$i] == $A[$j]) {
                $A[$i] = null;
                $A[$j] = null;
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:30:41 UTC, php, autosave

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:30:56 UTC, php, autosave

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:31:19 UTC, php, autosave

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:32:14 UTC, php, autosave

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null ) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:32:25 UTC, php, autosave

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:32:37 UTC, php, autosave

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:32:53 UTC, php, 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 25 26 27

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

User test case 1:

[2, 2, 2, 3, 3, 5, 7, 5, 7]

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data1

✔

0.008 s

OK
function result: 2

Code: 16:33:14 UTC, php, 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 25 26 27

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

User test case 1:

[2, 2, 2, 3, 3, 5, 7, 5, 7]

User test case 2:

[]

User test case 3:

[1]

User test case 4:

[4, 5]

User test case 5:

[1, 2, 1]

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data1

✔

0.004 s

OK
function result: 2

▶

test_data2

✔

0.004 s

OK
function result: 0

▶

test_data3

✔

0.004 s

OK
function result: 1

▶

test_data4

✔

0.004 s

OK
function result: 0

▶

test_data5

✔

0.004 s

OK
function result: 2

Code: 16:33:44 UTC, php, autosave

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        } e
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:34:00 UTC, php, autosave

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        } else print "debug\n";
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:34:01 UTC, php, 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 25 26 27

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        } else print "debug\n";
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

User test case 1:

[2, 2, 2, 3, 3, 5, 7, 5, 7]

User test case 2:

[]

User test case 3:

[1]

User test case 4:

[4, 5]

User test case 5:

[1, 2, 1]

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

stdout:

debug
debug
debug

expand all User tests

▶

test_data1

✔

0.004 s

OK
function result: 2

stdout:

debug
debug
debug
debug

▶

test_data2

✔

0.004 s

OK
function result: 0

▶

test_data3

✔

0.004 s

OK
function result: 1

▶

test_data4

✔

0.004 s

OK
function result: 0

▶

test_data5

✔

0.004 s

OK
function result: 2

stdout:

debug

Code: 16:34:46 UTC, php, autosave

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.
// print "this is a debug message\n";

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        } else 
        print "debug\n";
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Code: 16:34:54 UTC, php, 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 25 26 27 28

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        //if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
       // } else 
        print "debug\n";
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

User test case 1:

[2, 2, 2, 3, 3, 5, 7, 5, 7]

User test case 2:

[]

User test case 3:

[1]

User test case 4:

[4, 5]

User test case 5:

[1, 2, 1]

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

stdout:

debug
debug
debug
debug
debug
debug
debug

expand all User tests

▶

test_data1

✔

0.004 s

OK
function result: 2

stdout:

debug
debug
debug
debug
debug
debug
debug
debug
debug

▶

test_data2

✔

0.004 s

OK
function result: 0

▶

test_data3

✔

0.004 s

OK
function result: 1

stdout:

debug

▶

test_data4

✔

0.004 s

OK
function result: 0

stdout:

debug
debug

▶

test_data5

✔

0.004 s

OK
function result: 2

stdout:

debug
debug
debug

Code: 16:35:09 UTC, php, 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 25 26 27

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

User test case 1:

[2, 2, 2, 3, 3, 5, 7, 5, 7]

User test case 2:

[]

User test case 3:

[1]

User test case 4:

[4, 5]

User test case 5:

[1, 2, 1]

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data1

✔

0.004 s

OK
function result: 2

▶

test_data2

✔

0.004 s

OK
function result: 0

▶

test_data3

✔

0.004 s

OK
function result: 1

▶

test_data4

✔

0.004 s

OK
function result: 0

▶

test_data5

✔

0.004 s

OK
function result: 2

Code: 16:35:27 UTC, php, 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 25 26 27

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

User test case 1:

[2, 2, 2, 3, 3, 5, 7, 5, 7]

User test case 2:

[]

User test case 3:

[1]

User test case 4:

[4, 5]

User test case 5:

[1, 2, 1]

Analysis

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all User tests

▶

test_data1

✔

0.004 s

OK
function result: 2

▶

test_data2

✔

0.004 s

OK
function result: 0

▶

test_data3

✔

0.004 s

OK
function result: 1

▶

test_data4

✔

0.004 s

OK
function result: 0

▶

test_data5

✔

0.004 s

OK
function result: 2

Code: 16:35:30 UTC, php, final, score: 66

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

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

function solution($A) {
    $result = 0;
    $N = sizeof($A);
    if ($N > 1000000) return $result;
   
    for ($i = 0 ; $i < $N ; $i++) {
        if ($A[$i] != null && $N > 0) {
            for ($j = $N-1 ; $j > $i ; $j--) {
                if ($A[$j] != null && $A[$i] == $A[$j]) {
                    $A[$i] = null;
                    $A[$j] = null;
                    break;
                }
            }
        }
    }
    
    $A = array_filter($A);
    if (sizeof($A) == 1) {
        foreach($A as $a) $result = $a;
    }
    
    return $result;
}

Analysis summary

The following issues have been detected: timeout errors.

Analysis

Detected time complexity:

O(N**2)

expand all Example tests

▶

example1
example test

✔

0.004 s

expand all Correctness tests

▶

simple1
simple test n=5

✔

0.004 s

▶

simple2
simple test n=11

✔

0.004 s

▶

extreme_single_item
[42]

✔

0.004 s

▶

small1
small random test n=201

✔

0.008 s

▶

small2
small random test n=601

✔

0.012 s

expand all Performance tests

▶

medium1
medium random test n=2,001

✔

0.048 s

▶

medium2
medium random test n=100,003

✘

TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.13 sec.

6.000 s

TIMEOUT ERROR, running time: >6.00 sec., time limit: 0.13 sec.

▶

big1
big random test n=999,999, multiple repetitions

✘

TIMEOUT ERROR
running time: >6.00 sec., time limit: 0.99 sec.

6.000 s

TIMEOUT ERROR, running time: >6.00 sec., time limit: 0.99 sec.

▶

big2
big random test n=999,999

✘

TIMEOUT ERROR
running time: >7.00 sec., time limit: 1.15 sec.

7.000 s

TIMEOUT ERROR, running time: >7.00 sec., time limit: 1.15 sec.