CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 15 of 16

Hybrid View

  1. #1
    Join Date
    Oct 2009
    Posts
    7

    Array Duplicates

    Hi everyone, I'm new and will probably be asking a lot of questions from here on out. I have an assignment where the user inputs 10 integers into an array, then the program is supposed to output the numbers, but no duplicates. (ex. INPUT: 1 2 2 3 1 10 6 4 6 20 OUTPUT: 1 2 3 10 6 4 20)

    What I'm having trouble with is figuring out the algorithm needed to not cout the duplicates.

    Here's what I have...
    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
    int num[10];
    cout << "Enter 10 numbers...\n";
    
    for(int i=0; i<10;i++)
    cin >> num[i];
    And that's where I'm at. We are also not allowed to sort the array. I wanted to try something like

    Code:
    int n=0;
    for(int j=0; j<10;j++)
    {
        if(num[n] != num[n+1]
        cout << num[i]
        n++;
    
    }
    but since it isn't sorted, it will not check any previous numbers in the array, only the one next to it...

  2. #2
    Lindley is offline Elite Member Power Poster
    Join Date
    Oct 2007
    Location
    Seattle, WA
    Posts
    10,895

    Re: Array Duplicates

    Using an unordered_set (from TR1 or Boost) would fit the no-sorting requirement, but is probably not what the teacher had in mind.

    A naive solution would use two nested loops: The first would iterate over every entered element, and the second would check to see if that element exists earlier in the array. That would do it; however, it's going to be far less efficient than a sorting-based approach.

    If there's a relatively small maximum value which could be entered, you could use an array of bools to record whether you've seen a given value yet. Obviously this won't work too well if you have to handle negatives or all possible integers up to 2^32-1.

  3. #3
    Join Date
    Oct 2009
    Posts
    7

    Re: Array Duplicates

    Yes she did mention using two nested for loops. I'm having trouble with creating the algorithm in the 2nd for loop to check for duplicates. I can only really think of the way to do it if it was sorted.

  4. #4
    Join Date
    May 2007
    Location
    Scotland
    Posts
    1,164

    Re: Array Duplicates

    If it isn't to be sorted then you need some way of remembering the numbers that you have already come across. You could use a vector for this.

    What I'm thinking is that create a 'memory' vector, every number you read in, you check to see if it is in the 'memory' vector, if not, you add it to your 'memory' vector and print the value to the display, else you do nothing and a carry on to the next value.

  5. #5
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Array Duplicates

    http://www.cplusplus.com/reference/algorithm/remove/

    This should help. I doubt your teacher wants you to use this algorithm, but you can use its loop code.

    Simply start at index 0, and remove all numbers equal to num[0] in index 1 to 10. Repeat at index 1, 2 etc...

    Just remember that as you remove numbers, your array gets smaller.

  6. #6
    Join Date
    Oct 2009
    Posts
    7

    Re: Array Duplicates

    We can't use vectors (haven't learned them just yet) or remove the value from the array (asked not to, but this looks nice), only accepted way she was asking for was two for loops. I think I'm getting there though.

    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
    int num[10];
    bool is_dup = true;
    cout << "Enter 10 numbers..." <<endl;
    for (int i=0; i<10; i++)
    {
            cin >> num[i];
    }
    
    for (int j=0; j<10;j++) //repeats 10 times
    {
            for (int k=j; k>=0; k--) //this will repeat from j to 0
            {
                    if (num[j] != num[k]) //checks if one number isn't equal to others below it
                    is_dup = false; 
            }
            if (is_dup == false)
    }
    return 0;
    }
    I didn't finish it just yet. I just wanted to know if I'm making progress towards the right direction, and if what I'm doing makes sense.

  7. #7
    Join Date
    Oct 2002
    Location
    Austria
    Posts
    1,284

    Re: Array Duplicates

    The direction is right.
    You just have to set is_dup to false before the inner loop and set is_dup to true if the inner and outher value match.

    btw the inner loop should be
    Code:
    for (int k=j-1; k>=0; k--)
    to optimize the soluton a little you could break the inner loop when a duplicate was found

    Kurt

  8. #8
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Array Duplicates

    Quote Originally Posted by viperlasson View Post
    We can't use vectors (haven't learned them just yet) or remove the value from the array (asked not to, but this looks nice), only accepted way she was asking for was two for loops. I think I'm getting there though.

    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
    int num[10];
    bool is_dup = true;
    cout << "Enter 10 numbers..." <<endl;
    for (int i=0; i<10; i++)
    {
            cin >> num[i];
    }
    
    for (int j=0; j<10;j++) //repeats 10 times
    {
            for (int k=j; k>=0; k--) //this will repeat from j to 0
            {
                    if (num[j] != num[k]) //checks if one number isn't equal to others below it
                    is_dup = false; 
            }
            if (is_dup == false)
    }
    return 0;
    }
    I didn't finish it just yet. I just wanted to know if I'm making progress towards the right direction, and if what I'm doing makes sense.
    When you say "Cannot remove the value from the array", what exactly are you supposed to do? print them out as you find numbers, but only if they aren't duplicates?

    In this case, yeah, I guess you are in the right direction. Although I would say your check is inverted. Also, you need to start the loop at j-1, or you will test the number against itself.

    Code:
    is_dup = false; 
    for (int k=j-1; k>=0; k--) //this will repeat from j-1 to 0
    {
         if (num[j] == num[k]) //checks if one number is equal to others below it
      is_dup = true; //You found a duplicate.
    }
    if (is_dup == false) //No duplicates detected
        //do something
    else
        //do nothing

  9. #9
    Join Date
    Oct 2009
    Posts
    7

    Re: Array Duplicates

    Got it working, thanks for your help.

    Here is my code
    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
    int num[10];
    bool is_dup;
    cout << "Enter 10 numbers..." <<endl;
    for (int i=0; i<10; i++)
    {
            cin >> num[i];
    }
    
    for (int j=0; j<10;j++)
    {
            is_dup= false;
            for (int k=j+1; k<10; k++) //this will repeat from j-1 to 0
            {
                    if (num[j] == num[k]) //checks if one number is equal to others below it
                    is_dup = true; //You found a duplicate
            }
    
            if (is_dup == false)
            cout << num[j] << " ";
    
    }
    cout << endl;
    
    
    return 0;
    }
    edit: woops didnt really change some of my comments...
    Last edited by viperlasson; October 21st, 2009 at 12:57 AM.

  10. #10
    Join Date
    May 2009
    Posts
    2,413

    Re: Array Duplicates

    Quote Originally Posted by viperlasson View Post
    Got it working,
    Does it really work?

    Say you have the same number three times in the array. You find the number and look for duplicates. You'll find two duplicates. But then you'll find the number again and this time it has one duplicate.

    So how do you know if a number has already been counted as duplicate?

    ..X......X..........X........

    When you encounter any number, say X, you must first check so there are no X to the left. If there are, the X is already accounted for as duplicate and should be skipped.
    Last edited by nuzzle; November 2nd, 2009 at 04:54 AM.

  11. #11
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Array Duplicates

    Quote Originally Posted by nuzzle View Post
    Does it really work?

    Say you have the same number three times in the array. You find the number and look for duplicates. You'll find two duplicates. But then you'll find the number again and this time it has one duplicate.

    So how do you know if a number has already been counted as duplicate?

    ..X......X..........X........

    When you encounter any number, say X, you must first check so there are no X to the left. If there are, the X is already accounted for as duplicate and should be skipped.
    I agree with nuzzle. However, by now, I believe your program is too complicated. You should invest in writing helper functions:

    I would recommend these two functions:
    Code:
    bool isFirstOccurrence()
    int countOccurrences()
    If you know how to use iterators, I recommend this interface:
    Code:
    bool isFirstOccurrence(int* begin, int* end, int* valuePosition)
     int countOccurrences(int* begin, int* end, int value)
    else, use this one:
    Code:
     bool isFirstOccurrence(int array[], int size, int valueIndex)
      int countOccurrences(int array[], int size, int value)
    or even better, just use the corresponding std::algorithm

    with these two functions, this is what your code will look like:
    PHP Code:
    bool isFirstOccurrence(int array[], int sizeint valueIndex); //Prototype
    int countOccurrences(int array[], int sizeint value); //Prototype

    int main()
    {
        static const 
    int SIZE 10;

        
    int num[SIZE];
        
    cout << "Enter 10 numbers..." <<endl;
        for (
    int i=0i<SIZEi++)
        {
            
    cin >> num[i];
        }

        for (
    int i=0i<SIZEi++) //repeats 10 times
        
    {
            if (
    isFirstOccurrence(numSIZEi) == true)
            {
                
    int occurrences countOccurrences(numSIZEnum[i]);
                if (
    occurrences == 1)
                {
                    
    cout << num[i] << " appears only once." << endl;
                }
                else
                {
                    
    cout << num[i] << " appears " << occurrences << " times." << endl;
                }
            }
            
    //else do nothing
        
    }
    return 
    0;
    }

    bool isFirstOccurrence(int array[], int sizeint valueIndex)
    {
        
    //Write the actuall implementation
    }

    int countOccurrences(int array[], int sizeint value)
    {
        
    //Write the actuall implementation

    By doing this, not only is your code MUCH clearer, but the odds of you accidently leaving a bug in there gets much smaller too.

  12. #12
    Join Date
    May 2009
    Posts
    2,413

    Re: Array Duplicates

    Quote Originally Posted by monarch_dodra View Post
    By doing this, not only is your code MUCH clearer, but the odds of you accidently leaving a bug in there gets much smaller too.
    I agree in general but it's not that complicated. It's just two nested loops and a counter,
    Code:
    for (int i=0; i<SIZE; i++) {
       int n = num[i]; // a number
       int c = 0; // counter
       for (int j=0; j<SIZE; j++) {
          if (num[j] == n]) { // an occurance
             if (j<i) break; // already accounted for - skip
             else c++; // count
          } 
       }
       if (c>0) { // not skipped
          // c holds total number of occurrences of n
       }
    }

  13. #13
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Array Duplicates

    Quote Originally Posted by nuzzle View Post
    I agree in general but it's not that complicated. It's just two nested loops and a counter.
    Nice. Your code does have the advantage of being more efficient (no separate iteration for checking uniqueness and counting).

    The code isn't rocket science, that's for sure, but I feel it goes against the "don't write write-only code". While I'm sure writing the code is easy, it takes a little bit of concentration to figure out what it really does, especially if you have no idea what it is supposed to do to begin with.

  14. #14
    Join Date
    Oct 2009
    Posts
    7

    Re: Array Duplicates

    Bumping my thread for an updated version of this program. Now I need to not display any duplicates and count how many times a number was present in the array. It seems simple, but I can't understand where to reset the counter variable.
    Code:
    #include <iostream>
    using namespace std;
    
    const int SIZE = 3;
    int test[SIZE];
    int counter=1;
    bool is_dup;
    int main()
    {
    cout << "Enter three test grades: ";
    
            for (int i=0; i < SIZE; i++)
                    cin >> test[i];
    
            for (int j=0; j<SIZE; j++)
            {
                    is_dup = false;
                    for(int k=j+1; k<SIZE; k++)
                    {
    
                            if(test[j] == test[k])
                            {
                                    is_dup=true;
                                    counter++;       //this counts all the duplicates...
                            }
                    }
    
                    if (is_dup == false)
                    {
                            cout << test[j] << "        " << counter << "\n\n";
    //EDIT-ADDED        counter=1;
                    }
            }
    return 0;
    }
    I have my counter in there, but I need to reset it back to one after it finishes counting duplicates of a number. Don't know if I am doing this right so far.

    edit: Okay I'm solving it little by little, I just made it reset the counter after it prints the number + times it appeared, makes sense... Just now theres an issue where if you type in (1 1 1) it says it counts 4 duplicates in the array.

    I also have another question... I made my program to use an array of only 3 numbers. What if the user enters as many as they want, then a certain number to quit and print results? I know a while loop will be needed, but how will I increase the array size each time the user enters a test score?
    Last edited by viperlasson; November 1st, 2009 at 08:16 PM.

  15. #15
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: Array Duplicates

    Quote Originally Posted by viperlasson View Post
    Bumping my thread for an updated version of this program. Now I need to not display any duplicates and count how many times a number was present in the array. It seems simple, but I can't understand where to reset the counter variable.

    I have my counter in there, but I need to reset it back to one after it finishes counting duplicates of a number. Don't know if I am doing this right so far.

    edit: Okay I'm solving it little by little, I just made it reset the counter after it prints the number + times it appeared, makes sense... Just now theres an issue where if you type in (1 1 1) it says it counts 4 duplicates in the array.

    I also have another question... I made my program to use an array of only 3 numbers. What if the user enters as many as they want, then a certain number to quit and print results? I know a while loop will be needed, but how will I increase the array size each time the user enters a test score?
    Start your counter at 0, not 1.

    For your last question, you have two option:
    The bad one: Create an array with 1000 elements. Fill it in as the user goes, and remember how many items he has put it.
    The good one: Use a vector.

    I know your not supposed to use them, but really, if that is what you want to do, you don't have much of an option.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured