Repetition of elements

Question

I’m having difficulty generating as output the amount of elements repeated in the vector. Follow the code:

#include <stdio.h>
#include<stdlib.h>

int main()
{
    int N, i, temp, repetidos = 1;

    int *v1;

    printf ("Entre com N: ");
    scanf ("%d", &N);

    v1 = (int *)malloc(N * sizeof (int));

    temp = v1[0];

    for (i=1; i < M + 1; ++i){
        scanf ("%d", &v1[i]);

        if (v1[i] == temp){
            repetidos++;

            if (repetidos > 1){
                printf ("%d", repetidos);
            }
            temp = v1[i];
        }               
    }
}

Answer 1

If I understand correctly, you want the number that repeats in the vector. Example: {1, 2, 3, 3, 3} must return that 1 number repeats (the three). The vector {1, 3, 3, 2, 2, 1, 4, 4, 5} must return four, because four values are repeated in the vector (1, 2, 3 and 4).

In your case, it is unclear whether the vector is ordered. So I implemented Quick Sort to do this, which makes solving the problem much easier.

Also, it was unclear if the original vector could be modified. For this reason, I created a copy of it (v2) and ordered it. The variable repeticoesNumero is receiving the number of times a value appears in the array. If this value is greater than one, it means that the value repeats, and so increments the variable resposta, which at the end of the execution will have the number of repeating elements in the vector. Below the code:

#include <stdio.h>
#include <stdlib.h>
void quickSort(int a[], int l, int r) {
    int j;

    if(l < r)  {
        j = partition( a, l, r);
        quickSort(a, l, j-1);
        quickSort(a, j+1, r);
    }
}

int partition(int a[], int l, int r) {
    int pivot, i, j, t;
    pivot = a[l];
    i = l;
    j = r+1;

    while(1) {
        do
            ++i;
        while(a[i] <= pivot && i <= r);
        do
            --j;
        while(a[j] > pivot);
        if( i >= j ) break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    t = a[l];
    a[l] = a[j];
    a[j] = t;
    return j;
}
int main() {
    int n, i, temp, repeticoesNumero, resposta = 0;
    int *v1, *v2;

    printf ("Entre com n: ");
    scanf ("%d", &n);

    v1 = (int *)malloc(n * sizeof (int));
    v2 = (int *)malloc(n * sizeof (int));

    for(i = 0; i < n; ++i) {
        scanf("%d", &v1[i]);
        v2[i] = v1[i];
    }

    quickSort(v2, 0, n - 1);

    temp = v2[0];
    repeticoesNumero = 1;

    for (i = 1; i < n; i++) {
        if (v2[i] == temp) repeticoesNumero++;
        else {
            if (repeticoesNumero > 1) resposta++;
            temp = v2[i];
            repeticoesNumero = 1;
        }
    }
    if (repeticoesNumero > 1) resposta++;
    printf("%i numero(s) se repete(m) no vetor.\n", resposta);
}

I hope that’s it!

Just one observation: in your code there is a M in the loop for. I believe it was just a typo and the original value is N. My implementation is considering that it was a typo.

Answer 2

I’ll make a code as simple as it is for a beginner who doesn’t know and can’t do more complex things. In a professional code would be quite different, there would be functions, a proper data structure for this, probably with bits and other optimizations.

I would not do with ordering because of the cost and complexity of implementation.

As I said in my comments, I would need an auxiliary vector to indicate if there is a repetition. I hope the requirements are correct, I did according to what you gave to understand.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int N, repetidos = 0;
    printf("Entre com N: ");
    scanf("%d", &N);
    int *v1 = malloc(N * sizeof (int));
    int *aux = malloc(N * sizeof (int));
    int *flag = malloc(N * sizeof (int));
    int cont = 0;
    for (int i = 0; i < N; i++) {
        scanf ("%d", &v1[i]);
        int achou = 0;
        for (int j = 0; j < cont; j++) {
            if (v1[i] == aux[j]) {
                flag[j] = 1;
                achou = 1;
                break;
            }
        }
        if (!achou) {
            aux[cont] = v1[i];
            flag[cont++] = 0;
        }
    }
    for (int i = 0; i < cont; i++) repetidos += flag[i];
    if (repetidos > 0) printf ("\n%d repetidos", repetidos);
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

If you can discard the vector you can simplify a bit:

#include <stdio.h>
#include <stdlib.h>

int main() {
    int N, repetidos = 0;
    printf("Entre com N: ");
    scanf("%d", &N);
    int *v1 = malloc(N * sizeof (int));
    int *flag = malloc(N * sizeof (int));
    int cont = 0;
    for (int i = 0; i < N; i++) {
        int valor = 0;
        scanf ("%d", &valor);
        int achou = 0;
        for (int j = 0; j < cont; j++) {
            if (valor == v1[j]) {
                flag[j] = 1;
                achou = 1;
                break;
            }
        }
        if (!achou) {
            v1[cont] = valor;
            flag[cont++] = 0;
        }
    }
    for (int i = 0; i < cont; i++) repetidos += flag[i];
    if (repetidos > 0) printf ("\n%d repetidos", repetidos);
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

Answer 3

To find the number of repeats, there are some options:

• Use a Boolean vector also of size N to store visited houses. For each home of the original vector, search the remaining houses for repeats. If you find them, enter the positions in the boolean and increment the repeat counter (only once). When continuing the search, ignore the already visited houses.

• Or, sort the vector. So just sweep it and see if there are adjacent houses that are the same. If positive, increment the counter and continue to the next non-repeated box.