Let's say I have an array in the length of n, and the only values that can appear in it are 0-9. I want to create a recursive function that returns the number of different values in the array.
For example, for the following array: int[] arr = {0,1,1,2,1,0,1} --> the function will return 3 because the only values appearing in this array are 0, 1 and 2.
The function receives an int array and returns int something like this:
int numOfValues(int[] arr)
If you are using Java 8, you can do this with a simple one-liner:
private static int numOfValues(int[] arr) {
return (int) Arrays.stream(arr).distinct().count();
}
Arrays.stream(array) returns an IntStream consisting of the elements of the array. Then, distinct() returns an IntStream containing only the distinct elements of this stream. Finally, count() returns the number of elements in this stream.
Note that count() returns a long so we need to cast it to an int in your case.
If you really want a recursive solution, you may consider the following algorithm:
This should give you enough insight to implement this in code.
Try like this:
public int myFunc(int[] array) {
Set<Integer> set = new HashSet<Integer>(array.length);
for (int i : array) {
set.add(i);
}
return set.size();
}
i.e, add the elements of array inside Set and then you can return the size of Set.
public int f(int[] array) {
int[] counts = new int[10];
int distinct = 0;
for(int i = 0; i< array.length; i++) counts[array[i]]++;
for(int i = 0; i< counts.length; i++) if(counts[array[i]]!=0) distinct++;
return distinct;
}
You can even change the code to get the occurrences of each value.
You can try following code snippet,
Integer[] arr = {0,1,1,2,1,0,1};
Set<Integer> s = new HashSet<Integer>(Arrays.asList(arr));
Output: [0, 1, 2]
As you asked for a recursive implementation, this is one bad way to do that. I say bad because recursion is not the best way to solve this problem. There are other easier way. You usually use recursion when you want to evaluate the next item based on the previously generated items from that function. Like Fibonacci series.
Ofcourse you will have to clone the array before you use this function otherwise your original array would be changed (call it using countDistinct(arr.clone(), 0);)
public static int countDistinct(int[] arr, final int index) {
boolean contains = false;
if (arr == null || index == arr.length) {
return 0;
} else if (arr.length == 1) {
return 1;
} else if (arr[index] != -1) {
contains = true;
for (int i = index + 1; i < arr.length; i++) {
if (arr[index] == arr[i]) {
arr[i] = -1;
}
}
}
return countDistinct(arr, index + 1) + (contains ? 1 : 0);
}
int numOfValues(int[] arr) {
boolean[] c = new boolean[10];
int count = 0;
for(int i =0; i < arr.length; i++) {
if(!c[arr[i]]) {
c[arr[i]] = true;
count++;
}
}
return count;
}
Set, and then check the size of theSet