Finding duplicate values in array in c

Question

I am trying to find the duplicate values in an array. When a number is duplicated once like (25,25) program correctly prints 25 once but when a number duplicated twice like (12,12,12) program prints 12 three times while it should print it once.

 #include<stdio.h>
 int main()
{
    int numbers[15]={1,1,2,2,2,3,4,5,6,6,7,7,7,8,9},i,j;
    for(i=0;i<15;i++)
    {
        for(j=i;j<14;j++)
        {
            if(numbers[i]==numbers[j+1])
            {
                printf("Number %d has duplicate values\n",numbers[i]);
            }
        }
    }
    return 0;
}

Output:

Number 1 has duplicate values
Number 2 has duplicate values
Number 2 has duplicate values
Number 2 has duplicate values
Number 6 has duplicate values
Number 7 has duplicate values
Number 7 has duplicate values
Number 7 has duplicate values

The arrays cannot be assumed to be ordered so the program should work even with {1,2,1,2,3,4,2,5,6,6,7,7,7,8,9}.

Answer 1

In your example consider the indexes of the 7: they are 10, 11, 12.

The first print happens when i=10 and j=10 because your are indexing numbers[10] and numbers[11].

At the next iteration of the inner loop you have i=10 and j=11 and the condition is verified again by the elements numbers[10] and numbers[12].

Finally the third condition happens when i=11 and j=11 because you are referring to numbers[11] and numbers[12].

All this becomes clear if you print your indexes when the condition happens. For example you can substitute your printf with this:

printf("Number %d has duplicate values with indexes i=%d, j=%d\n",numbers[i], i,j);

which prints:

Number 1 has duplicate values with indexes i=0, j=0
Number 2 has duplicate values with indexes i=2, j=2
Number 2 has duplicate values with indexes i=2, j=3
Number 2 has duplicate values with indexes i=3, j=3
Number 6 has duplicate values with indexes i=8, j=8
Number 7 has duplicate values with indexes i=10, j=10
Number 7 has duplicate values with indexes i=10, j=11
Number 7 has duplicate values with indexes i=11, j=11

If your values are ordered you can do something like this:

#include<stdio.h>
 int main()
{
    int numbers[15]={1,1,2,2,2,3,4,5,6,6,7,7,7,8,9},i,j;
    int last_dup = -1;

    for(i=0;i<15;i++)
    {
        for(j=i+1;j<14;j++)
        {
            if(numbers[i]==numbers[j] && numbers[i]!=last_dup)
            {
                printf("Number %d has duplicate values with indexes i=%d, j=%d\n",numbers[i], i,j);
                last_dup = numbers[i];
                break;
            }
        }
    }
    return 0;
}

I initialized to -1 assuming your numbers are all positive. If not you can save the index of the last duplicate and reference using in the check numbers[last_dup_idx] (be careful to initialize the value properly and not go out the length of the array). I also added a break: since you already found a duplicate there is no need to continue the second loop.

If your array is not ordered, you can create an additional array saving the duplicates elements every time you find one and then iterate through this array to check.

FOR NOT ORDERED ARRAYS

#include<stdio.h>
 int main()
{
    int numbers[15]={1,1,2,2,2,3,4,5,6,6,7,7,7,8,9},i,j;
    int dups [7];//at most 15/2 duplicates
    char dup_idx=0;
    char found_new_duplicate; //initialized later
    for(i=0;i<15;i++)
    {
        for(j=i+1;j<14;j++)
        {
            if(numbers[i]==numbers[j])
            {
                found_new_duplicate = 1;

                //check in the duplicates array
                for (int kk=0; kk<=dup_idx; kk++)
                {
                    if (dups[kk]==numbers[i] && !(i==0 && j==1))
                    {
                        found_new_duplicate = 0;
                        break;
                    }
                }
                if (found_new_duplicate)
                {
                    dups[dup_idx] = numbers[i]; //insert the new duplicate in the duplicates array
                    printf("Number %d has duplicate values with indexes i=%d, j=%d\n",numbers[i], i,j);
                    printf("New duplicate %d\n", dups[dup_idx]);
                    dup_idx++;//increase the index
                    break;
                }
            }
        }
    }
    for (int kk=0; kk< dup_idx; kk++)
        printf("%d\n", dups[kk]);
    return 0;
}

Answer 2

A solution which doesn't introduce additional memory requirements and finds unique duplicates in a worst case of O(N²):

#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>

// macro that evaluates to the number of elements in an array:
#define SIZEOF_ARRAY(arr) sizeof(arr) / sizeof(*arr)

// contains() returns true if [values, values + size) contains value
bool contains(int *values, size_t size, int value)
{
    for (size_t i = 0; i < size; ++i)
        if (values[i] == value)
            return true;
    return false;
}

int main(void)
{
    int numbers[] = { 1, 1, 2, 2, 2, 3, 4, 5, 6, 6, 7, 7, 7, 8, 9 };

    for (size_t i = 0; i < SIZEOF_ARRAY(numbers) - 1; ++i)
    {
        if (contains(numbers, i, numbers[i])) // if we already encountered numbers[i]
            continue;                         // it was already identified as dup.

        if(contains(numbers + i + 1, SIZEOF_ARRAY(numbers) - i , numbers[i]))
            printf("Number %d has duplicate values\n", numbers[i]);
    }
}

Output:

Number 1 has duplicate values
Number 2 has duplicate values
Number 6 has duplicate values
Number 7 has duplicate values

Answer 3

The problem at hand is essentially simple. There is no need for any complicated code fragments. All it takes is just a little modification to the limits of the for loops and how you check for duplicates.

The solution:

Just introduce another array which is going to store the elements which are repeated in the array. Start filling this array from the 0th index as and when you find a NEWLY REPEATED element. This can easily be done iterating through this new array and checking if the currently encountered repeated element is already present or not. If it is not present there, then insert into the new array, which in the code I have given below is arr2[].

Hence whatever elements will be held by this new array are the unique repeated elements. I have attached the code and corresponding output below.

CODE:

#include<stdio.h>
int main()
{
    int numbers[15] = {1,1,2,2,2,3,4,5,6,6,7,7,7,8,9}, i, j;
    int arr2[15], k = 0, k1 = 0;
    int flag = 0;
    for(i = 0; i < 15; i++)
    {
       for(j = 0; j < 15; j++)
       {
           flag = 0;
           if(i != j && numbers[i] == numbers[j])
           {
               for(k1 = 0; k1 < k; k1++)
                   if(arr2[k1] == numbers[j])
                     flag = 1;
               if(flag != 1)
                   arr2[k++] = numbers[j];
           }
       }
    }
    for(i = 0; i < k; i++)
      printf("Number %d has duplicate values\n",arr2[i]);
    return 0;
}

OUTPUT:

Number 1 has duplicate values
Number 2 has duplicate values
Number 6 has duplicate values
Number 7 has duplicate values

Hope this helps.

Answer 4

If you deal with low numbers, you can always go via index table

#include <stdio.h>

int main() {

  int index[256] = {0};
  int table[15] = {1, 2, 3, 5, 5, 6, 1, 2, 9, 10, 11, 2, 3, 4, 5 };

  for(int i=0; i<15; i++) {
    index[table[i]] ++;
  }

  for(int i=0; i<256; i++) {
    index[i] > 1 ? printf("%d\n",i) : 0;
  }
}