Return the smallest unique value in a given array - C Language

Question

I'm not sure what sort of algorithm to apply here. My thoughts are that I should go about finding all the unique values first and then from there I should grab the minimum. However, I'm not sure how to implement this. I'm trying to do this in C.

The only constraints are that I can only use #include <stdio.h> #include <string.h>.

Answer 1

Using the algorithm you propose in your question (i.e. to first find all unique values and then find the lowest one), a possible implementation looks like this:

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

// NOTE: The second parameter array_size specifies the number of
// int elements in the array, NOT the size of the array in bytes.
int find_unique_min( int *array_start, int array_size )
{
    int *unique_values; //pointer to the dynamically allocated array with the unique values
    int num_unique_values; //number of values in the secondary array
    int minimum; //smallest unique value found so far
    int i, j; //loop counter variables

    // We don't know yet how many unique values there will be, so we don't know
    // how big the secondary array which holds the unique values must be.
    // However, in the worst case, every value is unique, which means that in
    // the worst case, the secondary array must have the same size as the 
    // primary array. Therefore, we make it the same size.
    unique_values = malloc( array_size * sizeof( int ) );
    if ( unique_values == NULL ) {
        fprintf( stderr, "Memory allocation error
" );
        return -1;
    }

    // This variable specifies the number of valid elements in the
    // secondary array, which must be set to zero for now.
    num_unique_values = 0;

    //fill secondary array with unique values
    for ( i = 0; i < array_size; i++ )
    {
        // compare the current array element with all other elements
        for ( j = 0; j < array_size; j++ )
        {
            // Since the comparison will say the values are identical when
            // comparing an element with itself, we must also check whether we
            // are comparing the element with itself.
            if ( array_start[i] == array_start[j] && i != j ) goto not_unique;
        }

        // We have now determined that the current array element is unique,
        // so we add it to the secondary array.
        unique_values[num_unique_values++] = array_start[i];

not_unique:
        continue;
    }

    //return -1 if no unique values were found
    if ( num_unique_values == 0 )
    {
        free( unique_values );
        return -1;
    }

    //find lowest value in secondary array and return it
    minimum = INT_MAX;
    for ( i = 0; i < num_unique_values; i++ )
    {
        if ( unique_values[i] < minimum ) minimum = unique_values[i];
    }

    free( unique_values );

    return minimum;
}

The only reason I included <stdlib.h> (which seems to be forbidden by the rules of your assignment) was because I needed to dynamically allocate memory for the secondary array to store the unique values. If you allocate a static array instead, you can get rid of that include directive. However, for a static array, the maximum number of unique numbers must be known at compile time (in order to determine how much memory to allocate).

Alternatively, you can combine both steps (finding the unique values and finding the minimum value) into one. That way, you don't need a secondary array and you also don't need to (dynamically) allocate memory for it. In that case, you also don't have to #include <stdlib.h>.

Combining both steps could be done using the following algorithm:

You can just go through the whole array from start to end (in a loop) and always remember (in a variable) the lowest unique value you have encountered so far. Whenever you encounter a lower value, you compare this value with all other elements of the array in order to determine whether it is unique. If it indeed is unique, you remember this new value instead of the previous one and continue with the rest of the array. At the end of the loop, you simply return the value of the variable which contains the lowest unique value you encountered.

An implementation of this algorithm could look like this:

#include <stdio.h>

#ifndef INT_MAX
#define INT_MAX 2147483647
#endif

// NOTE: The second parameter array_size specifies the number of
// int elements in the array, NOT the size of the array in bytes.
int find_unique_min( int *array_start, int array_size )
{
    int minimum; //smallest unique value found so far
    int i, j; //loop counter variables

    minimum = INT_MAX;

    for ( i = 0; i < array_size; i++ )
    {
        if ( array_start[i] < minimum )
        {
            // test if current element value is unique
            for ( j = 0; j < array_size; j++ )
            {
                if ( array_start[i] == array_start[j] && i != j ) goto not_unique;
            }

            minimum = array_start[i];
        }
not_unique:
        continue;
    }

    //if no unique value was found, return -1
    if ( minimum == INT_MAX ) return -1;

    return minimum;
}

Please note that normally, INT_MAX should not be defined manually. The only reason I did this is because of the restriction mentioned in the question which prevented #include <stdlib.h> from being used.