Test results - Codility

Tasks Details

easy

1. OddOccurrencesInArray

Find value that occurs in odd number of elements.

100%

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:

class Solution { public int solution(int[] 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 Java 8

Time spent on task 18 minutes

Notes

not defined yet

Task timeline

Code: 14:46:25 UTC, java, verify, result: Failed

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 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");
import java.util.HashMap;
import java.util.Map;
class Solution {
    public int solution(int[] A) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < a.length; i++) {
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
        }

        int result = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() % 2 == 1) {
                result = entry.getKey();
                break;
            }
        }
        return result;
    }
}

Analysis

Compile error

Solution.java:11: error: cannot find symbol
        for (int i = 0; i < a.length; i++) {
                            ^
  symbol:   variable a
  location: class Solution
Solution.java:12: error: cannot find symbol
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
                    ^
  symbol:   variable a
  location: class Solution
Solution.java:12: error: cannot find symbol
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
                                           ^
  symbol:   variable a
  location: class Solution
3 errors

Code: 14:46:33 UTC, java, verify, result: Passed

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 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");
import java.util.HashMap;
import java.util.Map;
class Solution {
    public int solution(int[] a) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < a.length; i++) {
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
        }

        int result = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() % 2 == 1) {
                result = entry.getKey();
                break;
            }
        }
        return result;
    }
}

Analysis

▶

example1
example test

✔

Code: 14:46:41 UTC, java, verify, result: Passed

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 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");
import java.util.HashMap;
import java.util.Map;
class Solution {
    public int solution(int[] a) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < a.length; i++) {
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
        }

        int result = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() % 2 == 1) {
                result = entry.getKey();
                break;
            }
        }
        return result;
    }
}

Analysis

▶

example1
example test

✔

Code: 14:46:45 UTC, java, final, score: 100

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 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");
import java.util.HashMap;
import java.util.Map;
class Solution {
    public int solution(int[] a) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < a.length; i++) {
            map.put(a[i], map.getOrDefault(a[i], 0) + 1);
        }

        int result = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() % 2 == 1) {
                result = entry.getKey();
                break;
            }
        }
        return result;
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

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

▶

example1
example test

✔

▶

simple1
simple test n=5

✔

▶

simple2
simple test n=11

✔

▶

extreme_single_item
[42]

✔

▶

small1
small random test n=201

✔

▶

small2
small random test n=601

✔

▶

medium1
medium random test n=2,001

✔

▶

medium2
medium random test n=100,003

✔

▶

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

✔

▶

big2
big random test n=999,999

✔