I'm trying to write a recursive function to find duplicates in an array of integers. For example if the array is: {4, 1, 4, 3, 2, 3} it should returns 2. I tried a mergesort-like approach but without success. Someone can help?
My try (works only with ordered arrays):
int count(int arr[], int bot, int top){
if(bot==top) return 0;
else{
int med = (bot+top)/2;
int n = count(arr, bot, med) + count(arr, med+1, top);
if(arr[med]==arr[med+1]) n++;
return n;
}
}
You are just checking if arr[med]==arr[med+1] which will have a problem when you have a case like 111 then the count will become two but the count should actually be one. So add an extra flag to check if the same element is repeated or not.
Sort the array. May be you can use merge sort or something to do that and then something like this should work!
#include <stdio.h>
int main(void) {
// your code goes here
int a[16] = {1,1,1,1,1,1,1,1,1,1,1,2,2,3,3,5};
int out = count(a,0,15);
printf("%d\n",out);
return 0;
}
int count(int arr[], int bot, int top){
int flag = 0;
if(bot==top) return 0;
else{
int med = (bot+top)/2;
int n = count(arr, bot, med) + count(arr, med+1, top);
if(arr[med]==arr[med+1])
{
flag = arr[med-1];
if(flag != arr[med])
n++;
}
return n;
}
}
