Recursive way to count distinct number of elements in array

Question

Let's assume I have this array: ARR = {5, 7, 3, 3, 7, 5} and I also have the size ( = 6 in this example ) so the recursive function should return 3.

this is the declaration of the function/method:

int f(arr, size);

I tried this thing:

count = 0;
if(size == 1)
   return 1;
if(x[i] != f(arr, size-1)
    count++;

return count;

but it doesn't work, as f(arr, size-1) doesn't walk through all the elements of the array and compare.

hopefully you guys could help!

Sweeper · Accepted Answer · 2019-06-08 08:23:42Z

Here's one way to do it:

private static int f(int[] arr, int size) {
    if (size <= 1) return 0; // there can't be duplicates if there are not even 2 elements!
    return f(arr, size - 1) + (inArray(arr, size - 1, arr[size - 1]) ? 1 : 0);
}

private static boolean inArray(int[] arr, int size, int elem) {
    if (size == 0) return false;
    return arr[size - 1] == elem || inArray(arr, size - 1, elem);
}

Basically the logic is this:

The size indicates the first N elements in arr that we actually care about.
If size is less than 2, we know there can't be any duplicates, so return 0.
Now for the recursion case, we return either 1 or 0 depending on whether the last element is in the rest of the array, plus whatever number of duplicates in the rest of the array ("the last element" means array[size - 1] and "the rest" means calling the function with size - 1.)
To determine whether an element is in an array, I used a recursive method as well, with a similar idea (check if the last element is elem, then check if the rest contains elem).

Collectives™ on Stack Overflow

Recursive way to count distinct number of elements in array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related