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
arrof sizen. It first takes in a positive integernfrom the user. Then readsnnumbers and stores them inarr. It checks and prints the number of repetitions inarr. The result is the sum of the total number of repetitions in the array.
Example: Ifarr=[4,3,4,4,3,4,5]
Then number of repetitions is6(which is 4 repetitions of4+ 2 repetitions of3)
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)
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.
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;
}
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);
}