I am unable to find the correct logic to find the number of repeated elements in an array. I can understand why my logic is not working, but I am not able to overcome it.

Following is the actual question:

Write a program that declares an integer array arr of size n. It first takes in a positive integer n from the user. Then reads n numbers and stores them in arr. It checks and prints the number of repetitions in arr. The result is the sum of the total number of repetitions in the array.
Example: If arr = [4,3,4,4,3,4,5]
Then number of repetitions is 6 (which is 4 repetitions of 4 2 repetitions of 3)

Following is my code:

#include <stdio.h>

int main() {
    int n, i, j, count = 1, p = 0;
    printf("Enter the length of array");
    scanf("%d", &n);
    int arr[n];
    for (i = 0; i < n; i  ) {
        printf("Enter a number\n");
        scanf("%d", &arr[i]);
    }
    for (i = 0; i < n; i  ) {
        for (j = i   1; j < n; j  ) {
            if (arr[i] == arr[j]) {
                count  ;
                break;
            }
        }
        if (count != 1) {
            p = p   count;
            count = 1;
        }     
    }
    printf("Number of repetitions are %d", p);
}

For the above code if we take the array as mentioned in the question, then each time my code encounters two same 4's, it counts both of them, hence my program ends up counting extra number of 4's. So I am unable to find some better logic to over come it.
(I am a beginner so I doesn't no much advanced function/methods used in C)

CodePudding user response：

One of the things that you can do is, keep an extra array for the numbers you have checked and each time when you compare numbers you would check if you have already seen this number or not.

I also want to include a few another approach to this problem. If we know that numbers in the list won't be so big we can use an array to keep track of counts.

//numbers = {4, 3, 4, 4, 3, 4, 5}
int max = findMaxValue(numbers);
int counts[max]; //should be done with dynamic memory allocation
for(i=0;i<max;i  ){
    counts[max] = 0;
}
for(i=0;i<numbers.size;i  ){
    counts[numbers[i]]  ;
}
int sum = 0;
for(i=0;i<max;i  ){
    if(counts[i] > 1){
        sum  = counts[i];
    }
}

Another thing that you can do is, sort the numbers first and then compare adjacent elements.

CodePudding user response：

I think it is a idea to put the same elements together first by sorting them.

#include<stdio.h>

int main() {
    int n = 0, count = 0;

    printf("Enter the length of array: ");
    scanf("%d", &n);

    int arr[n];

    for (int i = 0; i < n; i  ) {
        printf("Enter a number: ");
        scanf("%d", &arr[i]);
    }

    //sort
    for (int j = 0; j < n - 1; j  ) {
        for (int k = j   1; k < n; k  ) {
            if (arr[j] >= arr[k]) {
                arr[j] = arr[j] ^ arr[k];
                arr[k] = arr[j] ^ arr[k];
                arr[j] = arr[j] ^ arr[k];
            }
        }
    }

    // count
    int num = 1; // If you don’t want to include the repeated number itself, replace all "num = 1" with "num = 0"
    for (int j = 0; j < n - 1; j  ) {
        if (arr[j] == arr[j   1]) num  ;
        else {
            printf("The num %d repeats %d times\n", arr[j], num); // You can delete this line
            count  = num;
            num = 1; //Initialize num to avoid repeated accumulation of num and prepare to enter the next loop
        }
    }
    printf("Total repeats: %d\n", count);
    
    return 0;
}

CodePudding user response：

To avoid over-counting, you will need to keep track of which numbers have already been repeated. I wold just have a second array to save "already repeated" values:

#include <stdio.h>

int main()
{
    int n, p = 0, r = 0;

    printf("Enter the size of the array: ");
    scanf(" %u",&n);
    int arr[n];
    int rep[n - 1];
    for (int i = 0; i < n; i  ) {
        printf("Enter arr[%d]: ",i);
        scanf(" %d",&arr[i]);
    }
    for (int i = 0; i < n; i  ) {
        int count = 1, j;
        for (j = 0; j < r; j  ) {
            if (arr[i] == rep[j])
                break;
        }
        if (j < r)
            continue;
        for (j = i   1; j < n; j  )
            if (arr[i] == arr[j])
                count  ;
        if (count > 1) {
            p = p   count;
            rep[r  ] = arr[i];
        }     
    }
    printf("Number of repitions is %d\n",p);
}

CodePudding user response：

Let me learn you how to deal with such questions, by adding some lines to your source code:

#include <stdio.h>
int main()
{
    int n,i,j,count=1,p=0;
    printf("Enter the length of array");
    scanf("%d",&n);
    int arr[n];
    for(i=0;i<n;i  )
    {
        printf("Enter a number\n");
        scanf("%d",&arr[i]);
    }
    for(i=0;i<n;i  )
    {
        printf("Start for-loop for i, i=[%d]",i);
        for(j=i 1;j<n;j  )
        {
            printf("  Start for-loop for j, j=[%d]", j);
            if(arr[i]==arr[j])
            {
                printf("    Both arr[%d] and arr[%d] equal [%d]", i, j, arr[i]);
                count  ;
                printf("      As a result, count=[%d], p=[%d]", count, p);
                break;
            }
            else printf("    Arr[%d]<>arr[%d]: arr[i]=%d, arr[j]=%d, count=[%d], p=[%d]", i, j, arr[i], arr[j], count, p);
        }
        if(count!=1)
        {
            printf("  count=[%d] which is different than 1 while p=[%d]", count, p);
            p=p count;
            printf("  p has been increased by count and now, p=[%d]", p);
            count=1;
            printf("  count is brought back to 1");
        }     
    }
    printf("Number of repitions are %d",p);

}

JEZUS? All those printf() commands?
Yes: as a beginner you better put too much such commands than too less. One important thing: don't just read the output and start from there but first, try to imagine what you expect the output to be like. Like this, you'll immediately see where your expectations don't meet the real outcome and you'll know what you did wrong.

... and another important remark: once you're finished, don't remove those printf() lines, but put them into comment. If ever you might need to adapt your code to a changed requirement, you might need those printf() lines again.

CodePudding user response：

You are on the right track but your logic is incorrect: you do not count the last element of each repeated value.

• you should initialize count to 0 instead of 1
• you should iterate the inner loop from 0 instead of from i 1 to count the number of occurrences of arr[i] and continue to the end of the array, removing the break statement.
• you should just increment p if the count is not exactly 1, ie: if the element is repeated.

The time complexity of this approach is the same as yours, O(N²). You could lower the complexity to O(N.log(N)) by sorting the array and counting the duplicates in a single scan.

An even more efficient approach may reach linear time complexity: using a hash table, you would count the number of occurrences of each element read from the user. You would then enumerate the hash table, counting the number of non zero counts.

Here is a modified version:

#include <stdio.h>

int main() {
    int n, i, j, p = 0;

    printf("Enter the length of array: ");
    if (scanf("%d", &n) != 1)
        return 1;

    int arr[n];

    for (i = 0; i < n; i  ) {
        printf("Enter a number: ");
        if (scanf("%d", &arr[i]) != 1)
            return 1;
    }
    for (i = 0; i < n; i  ) {
        int count = 0;
        for (j = 0; j < n; j  ) {
            if (arr[i] == arr[j]) {
                count  ;
            }
        }
        if (count != 1) {
            p = p   1;
        }     
    }
    printf("Number of repetitions: %d\n", p);
    return 0;
}