CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
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. 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. Junior Member
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. ## 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. ## 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. Junior Member
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. ZuK
Senior Member
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. ## Re: Array Duplicates

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```

9. Junior Member
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. Junior Member
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";
}
}
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 07:16 PM.

11. ## Re: Array Duplicates

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.

12. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Array Duplicates

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.
Last edited by nuzzle; November 2nd, 2009 at 03:54 AM.

13. ## Re: Array Duplicates

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.

14. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Array Duplicates

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

15. ## Re: Array Duplicates

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.

#### Posting Permissions

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