-4

I want to make a program to find the repeating integers in an array. For that I had 2 methods.

  • Use nested array. it will give a time complexity of O(n²)
  • Use an auxiliary array to find the frequency of an array.

I have seen a solution, but it is limited to only 1 digit number. It uses a count array.

int *count = (int *)calloc(sizeof(int), (size - 2));

Why is it (size -2)?

The code is: 

#include<stdio.h>
#include<stdlib.h>
void printDuplicate(int arr[], int size){
    int *count = (int *)calloc(sizeof(int),(size-2));
    int i;
    for(i=0;i<size;i++){
        if(count[arr[i]] == 1)
            printf("%d,",arr[i]);
        else
            count[arr[i]]++;
    }
}
int main(){
    int arr[] = {2,5,3,4,2,5,7,8,7};
    int size = sizeof(arr)/sizeof(arr[0]);
    printDuplicate(arr,size);
    return 0;
}
Subinoy
  • 478
  • 7
  • 22
Gaurav Singhal
  • 148
  • 10

3 Answers3

1

Actually the calloc statement writen here is wrong. Here the memory allocation is

4*7=28

So here the memory allocation is for 7 integers but here you can access more that 7 elements. It is actually wrong in C language but it works fine with now a days compilers as C has no array boundary checking but it may cause to write invalid memory.

But how you are able to access the memory blocks which are not allocated?

This answer is explained in the best way here.

You can see the code I compiled here.

And when we decode the algorithm you can see that

  1. For i=0 the arr[0]=2. And then it checks whether the count[2]==1 or not as count[2] represents the number of repetitions for the number 2. As for the first time count[2]=0 so it increments the value to 1
  2. Then it check for all i values.
  3. When i=4 then it checks whether count[arr[4]] which is count[2]==1 or not. If it is one then it prints it.
Community
  • 1
  • 1
Subinoy
  • 478
  • 7
  • 22
0

Following comments show actual reason of each parameter for calloc function

int *count = 
(int *)
calloc(
    sizeof(int), // Number of elements to allocate
    (size-2) // Size of each element
);

I guess that your parameters are reversed

If you have:

int *count = (int *)calloc((size - 2), sizeof(int));

It would allocate an int array with size - 2 elements, each one with size of an int

But I think that this number of elements (size - 2) will be not enough for your program.

See your example (with reversed parameters):

...

int arr[] = {2,5,3,4,2,5,7,8,7}; // This array has 9 elements
int size = sizeof(arr)/sizeof(arr[0]); // So size will 9
printDuplicate(arr,size); // arr and 9 as parameters

...

int *count = (int *)calloc((size-2), sizeof(int)); // You allocated a 7-size array

...

if(count[arr[i]] == 1) // Maximum index of count will be 8
// so the allocated memory will be not enough

...

Source: calloc reference

emartinelli
  • 1,019
  • 15
  • 28
  • No. You can execute the same code for input int arr[] = {2,5,3,4,2,5,7,8,7,9,9}; the output is OK. You can check it on gcc. And the parameters I have passed in calloc are also correct, no error found by gcc, not even affecting the program. – Gaurav Singhal May 30 '15 at 06:28
  • I believe that @Subinoy answer (and edit) explains why there is no error on gcc. – emartinelli Jun 01 '15 at 11:38
  • Try to use a really big number (in my machine under 3000) in `arr[]` and you will have memory invasion. – emartinelli Jun 01 '15 at 11:59
0
int *count = (int *)calloc((size - 2), sizeof(int));

size -2 is not required, this is confused statement please avoid to use this.

Create memory as use all. Instead of size-2 we can use direct size of the array.

It won't make an error. Thank you.

Enjoy the learning this session.

cakan
  • 2,099
  • 5
  • 32
  • 42
narasimha
  • 1