Taking out number of subarrays from an array which contains all the distinct elements of that array

Question

I am a beginner in C. My teacher gave me a homework problem in which a user would provide an array with its size.

What we have to do is:-

1) Take out all the distinct elements from that array.

2) Compare all the subarrays which are possible in the main array with the "distinct array".

3) Tell the number of times we were able to successfully "discover" all those subarrays which contained ALL the distinct elements.

Example:- We are given an array :- [1,2,2,3,3] The distinct elements array would be :- [1,2,3] All the subarray of the original array will be :-

1) [1,2]
2) [1,2,2]
3) [1,2,2,3]
4) [1,2,2,3,3]   
5) [2,2]
6) [2,2,3]
7) [2,2,3,3]
8) [2,3]
9) [2,3,3]
10) [3,3]

The answer of this specific test case shall be 2. Since only (3) and (4) subarrays contain all the distinct elements i.e. 1,2 and 3.

Second Example:-

Given array :- [86,5,34,64,56,60,81,77,36,41]

The answer of the second example is 1; since all the elements of the original array are distinct and hence only one solution shall contain all the possible distinct elements which is the original array itself.

Here is my code which I have wrote for the above problem:-

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

bool check(int *, int *, int, int);


int main()
{
    int number; // Variable name "number" which will specify the size of dynamically allocated array.

    printf("Enter the size of your array\n");
    scanf("%d",&number);

    int *array;
    array = (int*)calloc(number, sizeof(int)); // Dynamically allocated memory.


    int *temp_array;
    temp_array = (int*)calloc(number, sizeof(int)); // Temporary variable of original array.

    int i,j=0; // Counter variables for loop.

    printf("Enter the elements of arrays\n");

    for(i = 0; i < number; i++)
    {
        scanf("%d",(array + i)); //Main original array being filled.
    }

    for(i = 0; i < number; i++)
    {
        *(temp_array + i) = *(array + i); //Copying into temp.
    }



    for(i = 0; i < number; i++)
    {
        for( j = i + 1 ; j < number; j++)
        {
            if( *(temp_array + i ) == *(temp_array + j))
            {
                *(temp_array + j) = 0; // My way of removing those numbers which are the repeated. (Assigning them value of zero).
            }
        }
    }

    i=0;j=0;

    int sub_number = 0;

    while(i < number)
    {
        if(*(temp_array + i) != 0)
        {
            sub_number++; // Variable name "sub_number" which will specify the size of dynamically allocated array "sub_array".
        }
        i++;
    }

    int *sub_array ;
    sub_array = (int*)calloc(sub_number,sizeof(int));

    j=0;
    for(i = 0;i < number ;i++)
    {
        if( *(temp_array + i ) != 0)
        {
            *(sub_array + j) = * (temp_array + i ); //Transferring all the distinct values from temp_array to sub_array.
            j++;
        }
    }

    free(temp_array); //Freed "temp_array". No longer needed.
    temp_array = NULL;

    for(i = 0;i < sub_number; i++)
    {
        printf("%d ",*(sub_array + i)); // Desired array which only contains distinct and unique variables.
    }

    printf("\n");

    int ans = 0;    //Variable which shall calculate the answer.
    int k=0;        //New variable counter
    j=0;


    for(i=0; i < number; i++) //This loop will traverse variable "i" on array "array".
    {
        k = i;
        while(k < number)   //This loop will traverse variable "k" on array "array"
        {
            int *new_array;
            new_array = (int*) calloc ((k-i+1),sizeof(int));

                for(j = i; j <= k; j++)  //This loop will assign the subset values of array "array" to array "new_array".
                {
                    *(new_array + (j - i)) = *(array + j);
                }
                if(check(new_array, sub_array, (k-i+1), sub_number) == true) //This will check if ALL the values in "sub_array" are present in "new_array" or not.
                {
                    ans++;
                }

            free(new_array);
            new_array = NULL;
            k++;
        }
    }

    printf("%d",ans);

    return 0;
}

bool check(int * new_array, int *sub_array, int new_number, int sub_number) //Function to check if ALL the values in "sub_array" are present in "new_array" or not.
{
    int i = 0;
    int j = 0;
    for(i = 0; i < new_number; i++)     //new_number is nothing but (k - i + 1)
    {
        if(*(new_array + i)  == *(sub_array + j))
        {
            j++;
            if(j == sub_number)
            {
                return true;
            }
            i = -1;
        }
    }
    return false;
}

How to optimise this code? Is there any better way to implement this?

Answer 1

Lack of Error Checking
There are two types of error checking that would improve the code. The first is checking user input, for instance if the value for the size of the array is negative the program will crash when it tries to allocate the memory for the array. The second is that the value returned from calloc(size_t count, size_t size) may be NULL if the call to calloc() fails for some reason. The function calloc() can fail if there is not enough memory to allocate the array.

It is generally a good practice to always check the return value of calloc(), while computers today have a lot of memory there are cases such as in embedded programming where there may not be enough memory.

    int *array;
    array = (int*)calloc(number, sizeof(int));
    if (array == NULL)
    {
        // report error and handle clean up
    }

Avoid Pointer Arithmetic When Possible
The code could just as easily use temp_array[i] as *(temp_array + i). Using an index is makes it easier to write, read and debug the code.

Pointers can be used to move through an array quickly in a linear fashion, but then it would be better to increment the pointer rather than adding an offset to the pointer.

DRY Code
There is a programming principle called the Don't Repeat Yourself Principle sometimes referred to as DRY code. If you find yourself repeating the same code multiple times it is better to encapsulate it in a function. One place where this code could be encapsulated is allocating memory for arrays. A function could take a number and return an allocated array of integers if the allocation doesn't fail.

Complexity
The function main() is too complex (does too much). As programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program.

There is also a programming principle called the Single Responsibility Principe that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

There are at least 3 possible functions in main().
- Allocate array memory
- Get the user input
- Copy distinct integers
- Calculate and print the answer

Algorithm
Rather than removing duplicates from the input array it might be better to go through the input array and copy a value to the sub_array only once. The check for zero is invalid since valid integers in the array can include zero and negative numbers.

Answer 2

Prefer to declare main() as a prototype:

int main(void)

---

Always, always check the return value of scanf() and family:

if (scanf("%d", &number) != 1) {
    fprintf(stderr, "Failed to parse a number\n");
    return EXIT_FAILURE;
}

Without such a test, the program will blindly proceed with whatever uninitialised value number has.

We should also ensure that a positive number was entered - if number is less than 0, then bad things are going to happen. Consider using an unsigned type for number, so that we're not converting between signed and unsigned (in calloc() calls).

---

Don't cast the result of malloc() family of functions. They return void*, which is assignable to a variable of any pointer type. I recommend using the variable itself as the argument to sizeof rather than repeating the type name - in many cases, it makes it easier for readers to see the correspondence.

And always, always check allocations don't return a null pointer.

int *array = calloc(number, sizeof *array);
if (!array) {
    fprintf(stderr, "Memory allocation failure\n");
    return EXIT_FAILURE;
}

---

*(array + i) is more conveniently and conventionally written as array[i] (or, perversely, as i[array] - but don't do that!).

---

I don't have time right now to follow the algorithm, but I'm sure it could be simpler. Fixing the issues above will certainly improve your C programs, anyway.

Answer 3

there are several memory leaks in the posted code.

This is because only some of the memory pointers (returned by calls to calloc() are being passed to free()

Suggest running valgrind (a free utility) as it will tell/show you all the memory leaks

When compiling, always enable the warnings, then fix those warnings. (for gcc, at a minimum use: -Wall -Wextra -Wconversion -pedantic -std=gnu11 ) Note: other compilers use different options to produce the same results.

Note that the function: calloc() expects it parameters to be of type size_t, not int nor unsigned int nor long int