Search code examples
arraysccontrolsgoto

How to check if an element of an array has already been inserted in that array in a "fashionable" way?


Context: An exercise asks me to:

  • Create an array of 20 elements;
  • Insert manually 20 numbers, ranging from 10 to 100 (these included), in said array;
  • If the inserted number (example: x) is not 10 <= x <= 100, print that it is not a valid number and prompt the user to reinsert a - valid - number;
  • Print the - valid - inserted number if it has been inserted for the first time (that is if the inserted number is not already present as an element of the array). If the number has been inserted already, do not consider it as one of the 'to be inserted' 20 numbers.

Problem: The issue is that, as you may notice watching the code, it is incredibly unoptimized as in "I couldn't think of a better way to solve this problem, but I do know that there must be an overall better way of doing this". Specifically though, I wasn't able to design a better way to check if the newly inserted number was already inserted before printing it (hence my question).

I have written the following code in which I think I have tackled all of the given tasks.

//Esercizio 6.15  ||| Pag. 277

#include <stdio.h>
#define SIZE 20

int main()
{
    int a[SIZE];
    int nums_left = 20;

    for_cycle:
    for(int i=0; i<SIZE; ++i){
        printf("Please insert %d numbers (whole)\n", nums_left);
        scanf("%d", &a[i]);

        //Managing Errors
        if(a[i]<10 || a[i]>100){
            printf("You have inserted a non valid value!\n");
            goto for_cycle;     //heresy! I know
        }

        //Effective execution of the printing  |  The Issue
        if(a[i]!=(a[i-1])){
            if(a[i]!=a[i-2]){
            if(a[i]!=a[i-3]){
            if(a[i]!=a[i-4]){
            if(a[i]!=a[i-5]){
            if(a[i]!=a[i-6]){
            if(a[i]!=a[i-7]){
            if(a[i]!=a[i-8]){
            if(a[i]!=a[i-9]){
            if(a[i]!=a[i-10]){
            if(a[i]!=a[i-11]){
            if(a[i]!=a[i-12]){
            if(a[i]!=a[i-13]){
            if(a[i]!=a[i-14]){
            if(a[i]!=a[i-15]){
            if(a[i]!=a[i-16]){
            if(a[i]!=a[i-17]){
            if(a[i]!=a[i-18]){
            if(a[i]!=a[i-19]){
            if(a[i]!=a[i-20]){
                printf("You have inserted: %d\n", a[i]);
            }}}}}}}}}}}}}}}}}}}

            //Updates of the variable 'numbers left to insert' accordingly
            nums_left--;

        }else{i--;}         //decrements the counter
    }
    return 0;
}

Solution

  • There are two main alternatives for tracking and testing which valid numbers have already been added:

    • search the array itself
    • maintain and use an external data structure for tracking the stored values

    You have implemented a slightly buggy and inelegant form of the first. Another answer, now deleted, demonstrated a correct and more elegant variation on this theme, using a nested loop to iterate over the array elements already assigned.

    In the speed for space tradeoff category, however, there are solutions of the second type. You might, for example, use a binary search tree to record the values added so far, and then search that instead of the main array. For so few total values, however, and such a small range of valid ones, a pretty good alternative would be to maintain a simple lookup table of which values had been recorded so far. For example:

    #include <stdio.h>
    
    #define SIZE 20
    #define MIN_VALID 10
    #define MAX_VALID 100
    
    int main(void) {
        int a[SIZE];
        _Bool seen[MAX_VALID + 1] = { 0 };
    
        for (int next_position = 0; next_position < SIZE; ) {
            printf("Please insert %d numbers (whole)\n", SIZE - next_position);
            scanf("%d", &a[next_position]);
    
            if (a[next_position] < MIN_VALID || a[next_position] > MAX_VALID){
                printf("%d is not a valid value!\n", a[next_position]);
            } else if (seen[a[next_position]]) {
                printf("You already inserted %d!\n", a[next_position]);
            } else {
                printf("You have inserted: %d\n", a[next_position]);
                seen[a[next_position]] = 1;
                next_position += 1;
            }
        }
    
        return 0;
    }