2

I am very new to C and I am hoping for some pointers. I am attempting to take an input of 7 integers of an array and search through them to see if any number appears only once. Here is what I have so far:

#define size 7
int main(void)
{
int array[size], target, i, prev, count;
//Initialize the array
printf("Please enter %d integers", size);
scanf("%d", &target);
prev = array[0];
count = 1;

for(i = 0; i<size; i++)
{
scanf("%d", &array[i]);
...

I realize it is quite terrible but C is completely strange to me. I figured out how to input the 7 integers from the user but I haven't the first clue as to where to start attempting to index them. I also realized that there are more advanced ways to figure it out; however, I am attempting find the solution using basic concepts that an amateur could understand.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
bardockyo
  • 1,415
  • 6
  • 21
  • 32
  • Don't forget to check that `scanf()` was successful. Once you have the array entered, you can do a brute force, quadratic search for duplicates by looking at the each value in the array in turn (one loop), and search through the rest of the array (a nested loop) to see whether any other value is equal to the current value from the outer loop. – Jonathan Leffler Sep 14 '12 at 06:04
  • hey for your reference i found one link with good explanation about this problem check it out http://stackoverflow.com/questions/7117388/finding-out-the-duplicate-element-in-an-array –  Sep 14 '12 at 06:06
  • Thanks that makes sense. Any idea how to check the array entered? Or how to index it? – bardockyo Sep 14 '12 at 06:06
  • "I am very new to C and I am hoping for some pointers." Ha! You got 'em :) – Richard Horrocks Jun 23 '14 at 22:50

4 Answers4

3

The simplest way to search for duplicates (though not the most efficient one) is to sort the array. You can use the built-in qsort function as such:

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

/* ... */

qsort (array, size, sizeof(int), compare);

int seen = 0;
for (int i = 1; i < size; ++i) {
  if (array[i] == array[i - 1]) {
    if (!seen) {
      printf("%d\n", array[i]);
      seen = 1;
    }
  } else {
    seen = 0;
  }
}
epsalon
  • 2,294
  • 12
  • 19
  • This takes `n log n + n` time. It beats n ^ 2 for large n !! –  Sep 14 '12 at 06:14
  • O(nlogn + n) = O(nlogn). This is doable in O(n) using a hashtable, but I figured that's too complicated for the poster's level of understanding. – epsalon Sep 14 '12 at 06:16
  • Right, espcially that his numbers are not ranged (so that an array cannot be used for hashing) and C doesn't provide `set` data structure –  Sep 14 '12 at 06:19
  • Right, if it were C++ or Java, I'd definitely go with a set-based implementation. – epsalon Sep 14 '12 at 06:20
  • +1 In general, this is the best strategy for finding duplicates. – Vinayak Garg Sep 14 '12 at 06:42
1

I know 3 methods to find duplicates, 2 are already answered, so here is the third (simplified)-

Complexity O(N) time, O(M) memory.

If the numbers are within some range like 0 - M and M is comparable to N the number of elements, you can use a array of size M+1 to check if the number has appeared before.

Code - 

int exists[M+1]; //set M to appropriate value
memset(exists, 0, sizeof(exists)); //set all 0 
for (i = 0; i < N; i++)
{
  if (exists[array[i]])
  {
    printf("Duplicate found\n");
    break; //or something else
  }
  exists[array[i]] = 1;
}

Note - Don't forget that input elements should be positive integers, not greater than M

Vinayak Garg
  • 6,518
  • 10
  • 53
  • 80
  • you can also use some kind of hashmap instead of bitmap, and when you have hash collision on some element you just compare current value with ones in the bucket, will increase amount of code significantly, but also should reduce memory consumption – Vorber Sep 14 '12 at 06:47
  • @Vorber: Of course, I mentioned the "simplified" approach for the OP. – Vinayak Garg Sep 14 '12 at 06:49
1

This one is a little pain in the neck to read, so I explain what I did a little bit here:

First, include the standard i/o library, #define array size to whatever you want, declare you array (I called mine: int entries[SIZE];).

The first for loop after "Enter 10 numbers" is the main one, that allows you to push the 10 numbers into the array.

The following if statements are tests that are applied to value entered right after is typed:

1) The first if statement makes sure we enter the value within the proper range.

2) The following 'else if' suggests that if entries[i] = entries[0] (meaning if this is the first object in the array) let's not do anything because there's nothing to compare it to.

3) The last 'else' contains a nested loop. The outer loop gets initialized to 1 so we make sure that in the comparison that takes place in the inner loop we're always comparing the current value against a previous one.

I hope this helps... cheers :)

*/

#include <stdio.h>

#define SIZE 10

//declarations
int entries[SIZE];

int main(void)
{
    printf("Enter 10 numbers:\n");

    for(int i = 0; i <= SIZE-1; i++)
    {
        printf("[%d]:\n", i);
        scanf("%d", &entries[i]);

        if(entries[i] < 10 || entries[i] > 100) {
            printf("Please enter valid number (between 10 and 100)\n");
            scanf("%d", &entries[i]);
        }
        else if(i == 0) {
            ;
        } else
        {
            for(int j = 1; j <= i; j++)
            {
                *//internal loop goes through all the previous entries (entries[i-1], entries[i-2], etc)*
                for(int k = 0; k < j; k++) {
                    if(entries[j] == entries[k])
                        printf("%d is a duplicate value\n", entries[i]);
                }
            }
        }
    }


}
Fsalad
  • 159
  • 1
  • 6
Antonella
  • 11
  • 1
0

This can be done in O(n^2) algorithm:

int yes = 1, i, j;
for (i = 0; i < n; ++i)
{
   for (j = i + 1; j < n; ++j) if (arr[i] == arr[j])
   {
       printf("Found a duplicate of %d\n", arr[i]);
       yes = 0;
       break;
   }
   if (!yes) break;
}
if (yes) printf("No duplicates");