No Duplicate Array C++

I need help to not allow duplicates in an array.

Page 1 of 1

13 Replies - 16271 Views - Last Post: 22 February 2010 - 05:04 AM Rate Topic: -----

#1 jtharrill  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 20-February 10

No Duplicate Array C++

Posted 20 February 2010 - 12:14 PM

I have worked on this problem for hours. I have tried to figure out the problem using a for loop to not allow the duplicates, but once I got to where one duplicate was being not allowed, a classmate suggested a while loop as the number of iterations is unknown because of possible duplicates and unallowed values.

The problem was to take 20 unique numbers and display in reverse order. I changed to 5 numbers for testing. I have got the sort(insertion sort), but the not allowing duplicates is the problem. At the moment it will only catch the first duplicate and the allows the following dupes. You can feel free to ignore the sorting and displaying. Here's my code. I moved the calling of the seach function to different places and still only catches the first dupe. I don't need a search function but I've tried it in the loop and it still only caught the first dupe. Also I would like to move the prompt out of the loop as to only display it once, but this causes the array to fill up with the first number entered.

#include <iostream>
#include <iomanip>
using namespace std;

int search( const int [], int, int);

int main()
{
 const int arraySize = 5;
 int data[ arraySize ]= {0,0,0,0,0};
 int insert;
 int input;
 int count = 0;
 
 

while (count < 5)
{
    cout << "Enter 5 unique numbers: ";
    cin >> input; 
    int element = linearSearch(data,input,arraySize);     

    if(element == -1 && input >= 10 && input <=100)
    {   
    data[count] = input;
    count++;
    }
    else if(element != -1)
    {
    cout << "Duplicate value." << endl;
    }
    else 
    {
    cout << "Invalid input" << endl;

    }

} 
//Display Unsorted Array
 cout << "Unsorted array:" << endl;
     
     for( int i = 0; i < arraySize; i++)
     {
     cout << setw(4) <<data[ i ];
     }
     
//insertion sort
 for( int next = 1; next < arraySize; next++)
 {
      
 insert = data[ next ];
 
 int moveItem = next;
 
 while ((moveItem > 0) && (data[ moveItem - 1] < insert ))
 {
 data[moveItem ] = data[ moveItem -1];
 moveItem--;      
}
data[ moveItem ] = insert;
}
cout << endl << "Sorted Array: " << endl;

for(int i = 0; i < arraySize; i++)
cout << setw(4) << data[ i ];

cout << endl;
system("pause");

}
//I don't think I need a function for this but am unable to figure it out either way.
int search(const int array[], int inputKey, int sizeOfArray)
{
    for ( int j = 0; j < sizeOfArray; j++)
    {  
          if(array[ j ] == inputKey)
          {
          return j;
          }
          else
          {
          return -1;               
          }
    }   
}     



Is This A Good Question/Topic? 0
  • +

Replies To: No Duplicate Array C++

#2 sarmanu  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 966
  • View blog
  • Posts: 2,362
  • Joined: 04-December 09

Re: No Duplicate Array C++

Posted 20 February 2010 - 12:26 PM

The following code may help you. It allows you to enter ONLY non-duplicate numbers in an array:
#include <iostream>

// Search for a duplicate
int search_duplicates(int const arr[], const int value, const int step)
{
	for (int i = 0; i < step; i++)
		if (arr[i] == value) // if we found the value in our array, it means that we found a duplicate
			return 1;
       
        // didn't find duplicate, return 0
	return 0;
}

int main()
{
	const int size = 5;
	int arr[size];
	int counter = 0;

	while (counter < size)
	{
		std::cout << "Enter value: ";
		std::cin >> arr[counter];
             
                // loop until a correct values was introduced
		while (search_duplicates(arr, arr[counter], counter))
		{
			std::cout << "Duplicate found, enter another value: ";
			std::cin >> arr[counter];
		}

		counter++;
	}

        // Print the array
	for (int i = 0; i < size; i++)
		std::cout << arr[i] << " ";

	return 0;
}


This post has been edited by sarmanu: 20 February 2010 - 12:31 PM

Was This Post Helpful? 1
  • +
  • -

#3 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: No Duplicate Array C++

Posted 20 February 2010 - 01:01 PM

Here is a link to a recursive reshuffle of an array that moves all duplicates in an UNSORTED array ... to the top of the array ...

recursive remove duplicates in an array
Was This Post Helpful? 1
  • +
  • -

#4 jtharrill  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 20-February 10

Re: No Duplicate Array C++

Posted 20 February 2010 - 02:13 PM

Yes, that helps alot. I understand how your code works, but why did the if statement not pick up the dupes? It's basically trying to mimic your code but only picks up the first duplicate. Is it possible to do the simple no duplicate with a if statement instead of a while loop. This is just for my understanding as I think I can make the program work correctly now.
Was This Post Helpful? 0
  • +
  • -

#5 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: No Duplicate Array C++

Posted 20 February 2010 - 02:39 PM

The simplest way to remove duplicates in an array is probably to pre-sort the array ...

Then, starting with the first pair, compare ... and if a match ... copy next ones over/down one ... and reset the top index --top

WHEN no match ... get next pair up ...

Do this ... until 'the pair' reaches the ever changing top

This post has been edited by David W: 20 February 2010 - 02:41 PM

Was This Post Helpful? 1
  • +
  • -

#6 jtharrill  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 20-February 10

Re: No Duplicate Array C++

Posted 20 February 2010 - 02:57 PM

View PostDavid W, on 20 February 2010 - 01:39 PM, said:

The simplest way to remove duplicates in an array is probably to pre-sort the array ...

Then, starting with the first pair, compare ... and if a match ... copy next ones over/down one ... and reset the top index --top

WHEN no match ... get next pair up ...

Do this ... until 'the pair' reaches the ever changing top



The trouble in my problem is that I need to not allow the value into the array and display a message of duplicate value. I pinpointed an error and will post in a minute to see if I can get some help understanding the concept.
Was This Post Helpful? 0
  • +
  • -

#7 sarmanu  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 966
  • View blog
  • Posts: 2,362
  • Joined: 04-December 09

Re: No Duplicate Array C++

Posted 20 February 2010 - 03:10 PM

I don't understand why you want to use 'if' instead of 'while'. 'While' assures that you will never insert a duplicate. If you insert a duplicate, an error will occur, and you will be prompted to enter a new value again. As a programmer, you don't have to stick with only one method, there are hundreds of methods to do this, just skip the 'if' one, which is not so good in your case.

This post has been edited by sarmanu: 20 February 2010 - 03:10 PM

Was This Post Helpful? 1
  • +
  • -

#8 jtharrill  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 20-February 10

Re: No Duplicate Array C++

Posted 20 February 2010 - 03:27 PM

View Postsarmanu, on 20 February 2010 - 02:10 PM, said:

I don't understand why you want to use 'if' instead of 'while'. 'While' assures that you will never insert a duplicate. If you insert a duplicate, an error will occur, and you will be prompted to enter a new value again. As a programmer, you don't have to stick with only one method, there are hundreds of methods to do this, just skip the 'if' one, which is not so good in your case.


I relize that I don't have to stick to the one method, but it was attempting to do the same thing as the while loop. I was just looking for some clarification as to why my if statement did not work. I think I found the error in the actual search function. It only works if I removed the brackets from the for statement and the if else I had in the actual search function. The if statement I had worked fine, the problem was in the seach function. Yet I do not get why including brackets would mess up the function. Any ideas? Can you not include brackets for a for statement if it only has one action? Does the if statement work that way also. Because if I take the else out of the search function and take the brackets out my original program worked fine.

But I did use your while loop and it works perfectly. I'm not trying to offend you just looking for the reasons why mine wasn't working. Just a few changes in the search function.

See my edited code with if statement.
#include <iostream> 
#include <iomanip> 
using namespace std; 
 
int search( const int [], int, int); 
 
int main() 
{ 
 const int arraySize = 5; 
 int data[ arraySize ]= {0,0,0,0,0}; 
 int insert; 
 int input; 
 int count = 0; 
  
  
cout << "Enter 5 unique numbers: "; 
while (count < 5) 
{ 
   
    cin >> input;  
    int element = search(data,input,arraySize);      
 
    if(element == 0 && input >= 10 && input <=100) 
    {    
    data[count] = input; 
    count++; 
    } 
    else if(element == 1) 
        cout << "Duplicate value." << endl; 
     
    else  
        cout << "Invalid input" << endl; 
 
     
 
}  
//Display Unsorted Array 
 cout << "Unsorted array:" << endl; 
      
     for( int i = 0; i < arraySize; i++) 
     { 
     cout << setw(4) <<data[ i ]; 
     } 
      
//insertion sort 
 for( int next = 1; next < arraySize; next++) 
 { 
       
 insert = data[ next ]; 
  
 int moveItem = next; 
  
 while ((moveItem > 0) && (data[ moveItem - 1] < insert )) 
 { 
 data[moveItem ] = data[ moveItem -1]; 
 moveItem--;       
} 
data[ moveItem ] = insert; 
} 
cout << endl << "Sorted Array: " << endl; 
 
for(int i = 0; i < arraySize; i++) 
cout << setw(4) << data[ i ]; 
 
cout << endl; 
system("pause"); 
 
} 
int search(const int array[], int inputKey, int sizeOfArray) 
{ 
    for ( int j = 0; j < sizeOfArray; j++) 
       
          if(array[ j ] == inputKey) 
                      return 1; 
          
          return 0;                
          
}     




Was This Post Helpful? 0
  • +
  • -

#9 jtharrill  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 20-February 10

Re: No Duplicate Array C++

Posted 20 February 2010 - 03:45 PM

For some reason including brackets and the else produced the error I was recieving. Is it wrong to include brackets if theres only one statement in the if statement?

For example this worked:
for (int i = 0; i < arraySize; i++)

 if (array[i] == key)

        return 1;

return 0;



Yet this didn't:
for (int i = 0; i < arraySize; i++)

{

         if (array[i] == key)

         {

                    return 1;

          }

         else

         {

          return 0

          }

}



This was the case for both the if statement I had and the while loop sarmanu showed

This post has been edited by jtharrill: 20 February 2010 - 03:57 PM

Was This Post Helpful? 0
  • +
  • -

#10 n8wxs  Icon User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: No Duplicate Array C++

Posted 20 February 2010 - 04:22 PM

Here's one way to get rid of the search function:

#include "stdafx.h"

#include <iostream>
#include <iomanip> 
#include <string>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	const int arraySize = 5; 
	int data[ arraySize ]= {0,0,0,0,0}; 
	int insert; 
	int input; 
	int count = 0; 

	int index = 0; // index into data[]

	cout << "Enter 5 unique numbers between 10 and 100: "; 

	while (count != arraySize) {		
		cin >> input;

		if (input < 10 || input > 100) {
			cout << "Invalid input. Try again." << endl; 
			continue;  // looping until user inputs valid number
		}

		for (index = 0; index < arraySize; index++) {
			if (data[index] == input) 
				break; // found duplicate, complain
		}

		if (index != arraySize) {
			cout << "Duplicate value. Try again" << endl;
			continue;  // looping until user inputs valid number
		}

		data[count++] = input; // copy unique valid number to array
	}

	//Display Unsorted Array 
	cout << "Unsorted array:" << endl; 

	for( int i = 0; i < arraySize; i++) 
	{ 
		cout << setw(4) << data[ i ]; 
	} 

	cout << endl;

	//insertion sort 
	for( int next = 1; next < arraySize; next++) 
	{ 

		insert = data[ next ]; 

		int moveItem = next; 

		while ((moveItem > 0) && (data[ moveItem - 1] < insert )) 
		{ 
			data[moveItem ] = data[ moveItem -1]; 
			moveItem--;       
		} 
		data[ moveItem ] = insert; 
	} 
	cout << endl << "Sorted Array: " << endl; 

	for(int i = 0; i < arraySize; i++) 
		cout << setw(4) << data[ i ]; 

	cout << endl; 

	system("pause");
	return 0;
}



This produces:

Quote

Enter 5 unique numbers between 10 and 100: 10
120
Invalid input. Try again.
20
30
10
Duplicate value. Try again
20
Duplicate value. Try again
40
50
Unsorted array:
10 20 30 40 50

Sorted Array:
50 40 30 20 10
Press any key to continue . . .


View Postjtharrill, on 20 February 2010 - 02:45 PM, said:

For some reason including brackets and the else produced the error I was recieving. Is it wrong to include brackets if theres only one statement in the if statement?

For example this worked:
for (int i = 0; i < arraySize; i++)

 if (array[i] == key)

        return 1;

return 0;



Yet this didn't:
for (int i = 0; i < arraySize; i++)

{

         if (array[i] == key)

         {

                    return 1;

          }

         else

         {

          return 0 <<<<<<<<<<<<<<<<<<<<<<<<<<<

          }

}



This was the case for both the if statement I had and the while loop sarmanu showed


You're missing a semi-colon
Was This Post Helpful? 1
  • +
  • -

#11 jtharrill  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 20-February 10

Re: No Duplicate Array C++

Posted 20 February 2010 - 04:40 PM

Even with the semicolon, that second segment fails to pick up duplicates past the first one. I don't understand why though.
Was This Post Helpful? 0
  • +
  • -

#12 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 281
  • View blog
  • Posts: 1,788
  • Joined: 20-September 08

Re: No Duplicate Array C++

Posted 20 February 2010 - 06:27 PM

EDIT: Sorry ... your problem is not yet clearly stated

Quote

The problem was to take 20 unique numbers and display in reverse order. I changed to 5 numbers for testing. I have got the sort(insertion sort), but the not allowing duplicates is the problem. At the moment it will only catch the first duplicate and the allows the following dupes. You can feel free to ignore the sorting and displaying. Here's my code. I moved the calling of the seach function to different places and still only catches the first dupe. I don't need a search function but I've tried it in the loop and it still only caught the first dupe. Also I would like to move the prompt out of the loop as to only display it once, but this causes the array to fill up with the first number entered.


1. What is your starting data? Are you given an array of 20 unique numbers to start? ... Just sort as you wish. (Bubble sort is fine for 20 numbers)

2. Let's say that is NOT the case ... then just sort the given array in the order you like ... do similar comparisons to those suggested in my post above ... and your are done when you have scanned that sorted array and moved unique numbers to one end over-top all the duplicates

3. If you need to enter non-duplicates ... from file or keyboard ... into a growing array of numbers ... you have been given code for that also ...

So ... what are your 'givens'?

This post has been edited by David W: 20 February 2010 - 08:10 PM

Was This Post Helpful? 0
  • +
  • -

#13 jtharrill  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 12
  • Joined: 20-February 10

Re: No Duplicate Array C++

Posted 22 February 2010 - 02:46 AM

The question was: "Use a one dimensional array to solve the following problem. Read in 20 numbers, each of which is between 10 and 100 inclusive. As each number is read validate it and store in the array only if it isn't a duplicate of a number. If it was a duplicate,output "duplicate number" and prompt the user to enter another number. If it was not between 10 and 100 output "invalid input".

Heres my finished code. Now I was just wondering why the brackets around the
search method made the code not work?

#include <iostream> 
#include <iomanip> 
using namespace std; 
 
int search( const int [], int, int); 
 
int main() 
{ 
 const int arraySize = 20; 
 int data[ arraySize ];
 int insert; 
 int input; 
 int count = 0; 
 int element = search(data,input,arraySize);
 
 
 //Initialize elements to 0.
 for(int i = 0; i < arraySize; i++)
         data[ i ] = 0;
 
//Prompt user for numbers.  
cout << "Enter 20 unique numbers: "; 
while (count < arraySize) 
{ 
   
    cin >> input;  
    element = search(data,input,arraySize);      
    //Ensure in range.
    if(element == 0 && input >= 10 && input <=100) 
    {    
    data[count] = input; 
    count++; 
    } 
    else if(element == 1)       //Ensure no duplicates.
        cout << "Duplicate value." << endl; 
     
    else  
        cout << "Invalid input" << endl; 
 
     
 
}  
//Display Unsorted Array 
 cout << "Unsorted array:" << endl; 
      
     for( int i = 0; i < arraySize; i++) 
     { 
       cout << setw(4) <<data[ i ]; 
     } 
      
//Insertion sort in decending order. 
 for( int next = 1; next < arraySize; next++) 
 { 
       
 insert = data[ next ]; 
  
 int moveItem = next; 
  
     while ((moveItem > 0) && (data[ moveItem - 1] < insert )) 
     { 
         data[moveItem ] = data[ moveItem -1]; 
         moveItem--;       
     } 
     data[ moveItem ] = insert; 
 } 

//Display Sorted Array.
cout << endl << "Sorted Array: " << endl; 
 
for(int i = 0; i < arraySize; i++) 
        cout << setw(4) << data[ i ]; 
 
cout << endl; 
system("pause"); 
 
} 

int search(const int array[], int inputKey, int sizeOfArray) 
{ 
    for ( int j = 0; j < sizeOfArray; j++) 
        if(array[ j ] == inputKey) 
                  return 1; 
                
        return 0;                
             
         
}     




Was This Post Helpful? 0
  • +
  • -

#14 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5932
  • View blog
  • Posts: 12,855
  • Joined: 16-October 07

Re: No Duplicate Array C++

Posted 22 February 2010 - 05:04 AM

View Postjtharrill, on 22 February 2010 - 03:46 AM, said:

Now I was just wondering why the brackets around the search method made the code not work?



If you mean your first search, its wasn't the braces, it was the condition.
int search(const int array[], int inputKey, int sizeOfArray) {
	for ( int j = 0; j < sizeOfArray; j++) {  
		if(array[ j ] == inputKey) {
			return j;
		} else {
			// if the above isn't true, this always happens
			return -1;               
			// you never run the rest of your loop
			// it will always stop at j==0
		}
	}   
}



I prefer to always use braces. Also, if you're doing a boolean check, use boolean:

// return true if item exists in array, false otherwise
bool contains(const int array[], int inputKey, int sizeOfArray) { 
	for (int i = 0; i<sizeOfArray; i++) {
		if(array[i] == inputKey) { return true; }
	}
	return false;
}     

//...

if(input < 10 || input >100) {
	cout << "Invalid input" << endl;
} else if (contains(data,input,arraySize)) {
	cout << "Duplicate value." << endl; 
} else {
	// you've passed all the tests, you win
	data[count++] = input; 
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1