Array Duplicates

Show 50 post(s) from this thread on one page
Page 1 of 2 12 Last
• October 19th, 2009, 11:23 PM
viperlasson
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...
• October 19th, 2009, 11:29 PM
Lindley
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.
• October 19th, 2009, 11:44 PM
viperlasson
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.
• October 20th, 2009, 02:33 AM
PredicateNormative
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.
• October 20th, 2009, 02:54 AM
monarch_dodra
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.
• October 20th, 2009, 03:09 AM
viperlasson
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.
• October 20th, 2009, 03:19 AM
ZuK
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
• October 20th, 2009, 03:35 AM
monarch_dodra
Re: Array Duplicates
Quote:

Originally Posted by viperlasson
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```
• October 21st, 2009, 12:52 AM
viperlasson
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...
• November 1st, 2009, 06:44 PM
viperlasson
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?
• November 2nd, 2009, 02:20 AM
monarch_dodra
Re: Array Duplicates
Quote:

Originally Posted by viperlasson
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.
• November 2nd, 2009, 03:31 AM
nuzzle
Re: Array Duplicates
Quote:

Originally Posted by viperlasson
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.
• November 2nd, 2009, 06:39 AM
monarch_dodra
Re: Array Duplicates
Quote:

Originally Posted by nuzzle
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 size, int valueIndex); //Prototypeint countOccurrences(int array[], int size, int value); //Prototypeint main(){    static const int SIZE = 10;    int num[SIZE];    cout << "Enter 10 numbers..." <<endl;    for (int i=0; i<SIZE; i++)    {        cin >> num[i];    }    for (int i=0; i<SIZE; i++) //repeats 10 times    {        if (isFirstOccurrence(num, SIZE, i) == true)        {            int occurrences = countOccurrences(num, SIZE, num[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 size, int valueIndex){    //Write the actuall implementation}int countOccurrences(int array[], int size, int 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.
• November 2nd, 2009, 09:55 AM
nuzzle
Re: Array Duplicates
Quote:

Originally Posted by monarch_dodra
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   } }```
• November 2nd, 2009, 10:17 AM
monarch_dodra
Re: Array Duplicates
Quote:

Originally Posted by nuzzle
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.
Show 50 post(s) from this thread on one page
Page 1 of 2 12 Last