C++: Removing a duplicate of the user input in an array

Question

I have been trying to solve this problem since yesterday. The program should accept N numbers from the user and will place them in an array. I have done this. However, I don't seem to know how to "warn" the user that the input is a duplicate and lets the user enter again. Here is my code:

# include <iostream>
using namespace std; 

int main () {
    
    int N, pos = -1, arr [N], i, j;
    int startLoop = 1;
    // the 'startLoop' variable is used so that the first user input can have the break function
    bool found = false;
    
    while (startLoop != 0) {
    
        cout << "Enter the number of integers to be entered: ";
        cin >> N;
        
            if (N <= 4) {
                cout << "Invalid. \n";
            }
            
            if (N > 4) {
                cout << "\n\nEnter " << N << " unique numbers: " ;
                for (i = 0; i < N; i++) {
                    cin >> arr [i];     
                    
                    for (j = 0; j < N && !found; j++) {
                        if (arr [j] == arr [i]) {
                            found = true;
                            cout << "Enter again: ";
                        }
                    }
            
            break;
            }
    }
}

Answer 1

The following is the copy paste of your code:

1. By adding break you will jump out of the outer for loop and you cannot read n inputs.

2. the inner loop range is not correct since i is the total number of values read by now. i.e. if N= 10 and in third iteration you are trying to loop among 10 elements to double check if the latest number is a duplicate, while you have read 3 elements by now.

   if (N > 4) {
      cout << "\n\nEnter " << N << " unique numbers: " ;
      for (i = 0; i < N; i++) {
         cin >> arr [i];                    
         for (j = 0; j < N && !found; j++) {
           if (arr [j] == arr [i]) {
             found = true;
             cout << "Enter again: ";
           }
         }
         break;
      } 
   

   }

How to fix?

• One approach would be to read the input in a separate loop and then try to find the duplicates and remove them.

• Time Complexity will be O(n) since you need to traverse through the list twice, however you need to implement removing elements from the array efficiently without shifting all the elements

• Second approach is like what you are trying to implement but it is not efficient since every time a user is adding a new elements you need to re-evaluate i numbers (in worst case n numbers when you are filling the end of array). this process should be repeated every time user insert a repeated number.

• The best approach would be store all input numbers inside a hash (set) and every-time a new number is inserted check whether it is already suggested by the user or not. Time complexity of searching elements through unordered_set will be O(1)

Answer 2

Problems:

Your code has many several problems:

1. You shouldn't use VLAs (Variable Length Arrays) as they are non-standard.
2. Using N before initializing it is UB (Undefined Behaviour).
3. Your approach is not efficient as it checks on average n/2 elements n times and therefore it has a time complexity of O(n^2).
4. You have many unused variables and variables that should be in a more specific scope.

Solutions:

1. Use std::vector insted of VLAs.
2. Resize the vector after initializing N.
3. Change your approach.
4. Change the scope of your variables.

Additional information:

1. using namespace std; is considered a bad practice (More info here).
2. You should probably add input checking to std::cin to verify that the input is a number.

Full code: Checking duplicates once at the end of input with std::vector (Time complexity: O(n * log(n)). Space complexity: O(n)):

#include <iostream>
#include <vector>
#include <algorithm>

bool hasDuplicates(std::vector<int> toCheck)
{
    std::sort(toCheck.begin(),toCheck.end());
    for(unsigned int i = 1; i < toCheck.size(); i++)
        if(toCheck[i] == toCheck[i-1])
            return true;
    return false;
}

int main () {
    std::vector<int> arr;
    int N;

    while (true) {
        std::cout << "Enter the number of integers to be entered: ";
        std::cin >> N;
        if (N <= 4) {
            std::cout << "Invalid: The number of integers to be entered must be bigger than 4. \n";
        }
        else {
            arr.resize(N);
            std::cout << "\n\nEnter " << N << " unique numbers: " ;
            for (int i = 0; i < N; i++)
                std::cin >> arr [i];
            if(hasDuplicates(arr))
                std::cout << "Invalid: The numbers must be unique. \n";
            else
                break;
        }
    }
}

Checking duplicates each time a number is entered with std::unordered_map (Time complexity: Amortized O(n). Space complexity: O(n)):

#include <iostream>
#include <vector>
#include <unordered_set>

int main () {
    std::vector<int> arr;
    std::unordered_set<int> alreadyAppeared;
    int N;
    std::cout << "Enter the number of integers to be entered: ";
    std::cin >> N;
    while (N <= 4) {
        std::cout << "Invalid: The number of integers to be entered must be bigger than 4. \n";
        std::cout << "Enter the number of integers to be entered: ";
        std::cin >> N;
    }
    arr.resize(N);
    std::cout << "\n\nEnter " << N << " unique numbers: \n";
    for (int i = 0; i < N; i++)
    {
        int entering;
        std::cout << "Enter unique number: ";
        std::cin >> entering;
        if(alreadyAppeared.find(entering) == alreadyAppeared.end())
        {
            alreadyAppeared.insert(entering);
            arr[i] = entering;
        }
        else
        {
            std::cout << "Invalid: The numbers must be unique. \n";
            i--;
        }
    }
}