menu

Questions & Answers

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;
}
Comments:
2023-01-11 09:13:00
Well, goto is not as evil as you might think now, but here it is plain wrong. You'd re-start the loop with index 0 if it actually comes to action...
2023-01-11 09:13:00
bool inserted[100-10+1] = {0}; and later if(inserted[num-10]) { /*already inserted*/ } else { inserted[num-10] = true; } Loop through the array afterwards to list those inserted.
2023-01-11 09:13:00
a[i] != a[i-X] will access the array out of bounds (undefined behaviour!) for any i < X!
2023-01-11 09:13:00
Make an extra array z of 91 elements and set it all to zeros. Once x is "inserted", set z[x-10] to 1. To check if element x was already inserted, check z[x-10].
2023-01-11 09:13:00
Oh, I see @TedLyngmo already proposed that...
2023-01-11 09:13:00
Note that @TedLyngmo 's approach is pretty nice for a small range of numbers, as in your case. The other variant would be iterating over the values already inserted with a nested loop: for(size_t i = 0; i < SIZE; /* no automatic increment!) { a[i] = ...; for(size_t j = 0; j < i; ++j) { if(a[j] == a[i]) { goto INSERTED; } } ++i; INSERTED:; } – so you iterate over the values already inserted and only if not found you switch to next i. Other loop variants possible, too...
2023-01-11 09:13:01
@Gisvaldo "... the following code in which I think I have tackled all of the given tasks." --> what code did the "Set all the elements of the array to 0"?
2023-01-11 09:13:01
@chux-ReinstateMonica Indeed, this part actually is missing – though, provided the variant above is fixed appropriately, it would be meaningless anyway as the values would always get overwritten without ever having been read before. If I were the teacher I'd accept this part missing if explained correctly why it has been skipped...
2023-01-11 09:13:01
@Aconcagua "always get overwritten" Usually, expect when scanf() returns EOF or 0, then OP's code is UB.
2023-01-11 09:13:01
You are not checking the result of scanf – note that you cannot get out of that loop at all any more if some user provides invalid input like e.g. 10sss – if so, then each next loop will not read any further input once 10 has been scanned as sss cannot get converted to an integer and thus won't be consumed. Not sure if appropriate error handling is required by the task, but it is a good idea to get used to consider this possibility right from the start with every new task.
2023-01-11 09:13:01
If doing so (bonus points?) you might always read an entire line of text with fgets and use sscanf afterwards to extract the actual number.
2023-01-11 09:13:01
@chux-ReinstateMonica Oh, right, of course, a[i] might not have been written to at all – have been inattendent... Seems as if me being too much used to already doing the error handling myself ;)
2023-01-11 09:13:01
@Aconcagua Deeper, the point being array initialization to 0 effectively fills the array with invalid values for this task, thus if scanf() does return 0 or EOF due to end-of-file, no UB in the if(a[i]<10 || a[i]>100){, yet certainly an infinite loop as you suggest. I suspect the meaningless zero initialization was crafted for this learner task. Somewhat necessary when weak code does not check return values.
Answers(2) :

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;
}

Given that the range of numbers is limited to 91 options, it is reasonable to create an array of bool initialized to false to store flags to determine if a number has been entered.

On each number being added, if the corresponding flag is false, accept the number and change that flag to true.

A simple implementation of this idea might look like:

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

#define N 20
#define LOWER 10
#define UPPER 100

int main(void) {
    bool flags[UPPER - LOWER + 1] = { false };
    int input_numbers[N];

    for (size_t i = 0; i < N; i++) {
        while (true) {
            int n;

            if (scanf("%d", &n) != 1) {
                printf("Please enter a number.\n");
                while (getchar() != '\n');
                continue;
            }
       
            if (n >= LOWER && n <= UPPER && !flags[n-LOWER]) {
                input_numbers[i] = n;
                flags[n-LOWER] = true;
                break;
            }
            printf("Invalid input.\n");
        }
    }

    return 0;
}