2

The problem I'm trying to solve is checking an array as the user is inputting values into the array. The specific instructions are: to use a separate method to do the checking; the method must sort the array first; the duplicate check has to be performed in real-time, meaning the user won't first enter all values then the array go back and check them. I've looked around and while I've figured out how to sort, I am completely stumped as to how to check for duplicates as each value is entered. Can anyone nudge me in the right direction of thinking?

This is what I came up with, working within the limits of the assignment:

void getLottoPicks(int numbers[])
{
    cout << "Please enter your 7 lotto number picks between 1 and 40: " << endl;

    for (int i = 0; i < SIZE; i++)
    {
        cout << "Selection #" << i + 1 << endl;
        cin >> numbers[i];
        while (numbers[i] < 1 || numbers[i] > 40)
        {
            cout << "Please choose a number between 1 and 40: " << endl;
            cin >> numbers[i];
        }
        for (int j = 0; j < i; j++)
        {
            while (numbers[i] == numbers[j])
            {
                cout << "You have already picked that number. Enter a different one: " << endl;
                cin >> numbers[i];
            }
        }
    }
}

It compiles and runs without any bugs (none that I've caught yet, anyway). If anyone has any feedback it'd be appreciated. I know this kind of algorithm is highly inefficient but our arrays are only 7 values long and this is what was asked for. Initially I thought it had to be sorted, but that was only required if we chose to do the check in a different function.

Improve this question
3
  • Can't you just search the array for duplicate? Get a value, check if it has already been entered, and then either add it to the rest of the values or display an error message. Commented Nov 17, 2013 at 5:46
  • 3
    There's also std::sort and std::unique. Commented Nov 17, 2013 at 5:52
  • There's also std::set... :P Add the values to a set, then copy them to an array once the input's done, if you simply must have an array. Commented Nov 17, 2013 at 6:03

3 Answers 3

Reset to default
2

There are many options by which you can do that.

  1. First of all , if you are using only array , use std :: sort and std :: unique.

  2. If the largest number in array is not very big you can maintain a bool array , which you can set to 0. 

       #include <cstring>
   bool a[100000];
   memset(a,0,sizeof a)

  main(){
  int x,i,arr[1000];
  while(cin>>x){
     if( a[x] == 0)
     arr[i++]=x,a[x]=1;
  }

Before entering the value in array check if the index value of a for that number is 0.
If it is 0 enter the value in the array ,mark that index of boolean array 1. Later you can sort using

      #include<algorithm>
      sort(arr,arr+(size of arr));

3.You can maintain a set to enter values , instead of an array it will be a binary tree and will discard any dupicate values and the values after insertion will be in a sorted order.

      #include <set>
       set <int> arr;
      main(){
        int x;
        while(cin>>x)
        a.insert(x);
      }

You can get values from the set using an iterator like 

      set<int> :: iterator it;
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Given that he has to maintain a sorted array, the bool array is probably overkill. He only has to check values through his array until he gets to a value larger than or equal to the value he's checking.
1
  1. Get first input. Put it in the array.
  2. Get another input. Check to see it doesn't match anything else already in the array. If it does, discard it. If it doesn't, put it in the array in order (so the array stays sorted).
  3. Repeat step 2.

Alternatively, if the assignment allows it, use a set.

And if you're not allowed to use a set, use a vector. A vector will allow you to insert elements easily at a specific index to help keep things sorted. And it will auto-resize as you add elements to it.

Improve this answer

2 Comments

If you're using the latter (a vector), insert each new element after an iterator request from std::upper_bound. It requires the sequence is sorted (and it will be if you do this every time) and uses a binary search for the correct location. The search is O(logN), but the insertion itself will still be linear, even with optimized shifting with something like std::rotate.
@nhgrif I went ahead and followed your steps and came up with this bit of code (edited into my question). Thank you for the help.
0

Since your numbers are integer between 1-40, you can use a trivial and fast solution (O(1)). And you can reuse this trick to do the sorting later. Here's the main lines:

  • Create an array of boolean with 40 elements initialized at false. I'll call it vals.
  • Every time you read a value, check the value of vals[input_value]. If it's true, it's a duplicate, otherwise set it to true.
  • Now, in order to sort the values, you simply do a for-loop from 1 to 40 and if vals[i] is true, then put in an other array or print it.

This is my solution:

void getLottoPicks(int numbers[])
{
    cout << "Please enter your 7 lotto number picks between 1 and 40: " << endl;
    int value;
    bool vals[41];
    for (int i = 0; i <= 40; i++) vals[i] = false;

    for (int i = 0; i < SIZE; i++)
    {
        cout << "Selection #" << i + 1 << endl;
        bool input_ok = false;
        while (!input_ok)
        {
            cin >> value;
            if (value < 1 || value > 40) {
                cout << "Please choose a number between 1 and 40: " << endl;
            } else if (vals[value]) {
                cout << "You have already picked that number. Enter a different one: " << endl;
            } else {
                input_ok = true;
            }
        }
        vals[value] = true;
    }

    int j = 0;
    for (int i = 1; i <= 40; i++) {
        if (vals[i]) {
            numbers[j++] = i;
        }
    }
}

This algorithm is inspired by the Counting Sort algorithm. The Counting Sort algorithm is a very easy and efficient algorithm that can be used when the elements are small integers.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.