Distinct

This post covers the generation of a solution for the Codility_ problem Distinct. If interested I suggest you read the requirements from the Codility_ web site, work on your solution, and if needed look at he the code in this post which is also in GitHub.

Distinct
Compute number of distinct values in an array.
https://app.codility.com/programmers/lessons/6-sorting/distinct/

We are given an array of integers with different values. Our task is to return the number of distinct values.

We will solve this problem using Java and the VSCode IDE on a WIndows computer. The simplest way is to solve the problem using the IDE provided by Codility_.

Since we will solve the problem on a different platform, we will require to generate a test scaffold. Such code IS NOT PART OF THE SOLUTION. When done we will need to copy the code into the Codility_ IDE for approval.

2, 1, 1, 2, 3, 1
main <<< arr: [2, 1, 1, 2, 3, 1]
<<< hm: {1=1, 2=1, 3=1}
main <<< output: 3


1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3
main <<< arr: [1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
<<< hm: {1=1, 2=1, 3=1}
main <<< output: 3


69
main <<< arr: [69]
main <<< output: 1

We have three test cases.

The first input line holds the values for the integers. Our test code seems to generate an array with the values. The contents of the array are then displayed to make sure all is well before calling the function of interest.

The function of interest is called. It seems to display the contents of a hashmap. The hashmap has three distinct elements. The answer appears to be 3. The value returned by the function of interest seems to match our expectations.

Two other test cases follow.

    /**
     * Test scaffold.
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {

        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read int[] array ****
        int[] arr = Arrays.stream(br.readLine().trim().split(", "))
                        .mapToInt(Integer::parseInt)
                        .toArray();

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<< arr: " + Arrays.toString(arr));

        // **** call function of interest and display result ****
        System.out.println("main <<< output: " + distinct(arr));
    }

Our test code seems to read the input line and populate an int[] array with the values.

The contents of the array are then displayed.

The function of interest is called and the result displayed. The test code seems simple and to the point. Note that the test code IS NOT PART OF THE SOLUTION.

    /**
     * Given an array A consisting of N integers, 
     * return the number of distinct values in array A.
     * 
     * Execution: O(n) - Space: O(n)
     */
    static public int distinct(int[] arr) {

        // **** sanity check(s) ****
        int len = arr.length;
        if (len == 0) return 0;
        if (len == 1) return 1;

        // **** initialization ****
        HashMap<Integer, Integer> hm    = new HashMap<>();
        Integer val                     = null;

        // **** traverse array counting different values - O(n) ****
        for (int v : arr) {
            Integer cnt = hm.get(v);
            if (val == null) hm.put(v, 1);
            else hm.put(v, ++cnt);
        }

        // ???? ????
        System.out.println("<<< hm: " + hm.toString());

        // **** return number of distict values ****
        return hm.size();
    }

We start by performing some sanity checks.

We then initialize a hashmap and an auxiliary variable.

We enter a loop in which every value in the array is entered into the hashmap. Each time we keep an accurate count of each integer.

When all is said and done we return the number of unique values which is the size of the hashmap.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.

Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.

Enjoy;

John