Filling an array with unique numbers

[EnGxSoLiD]

Hi there
This is my homework , I solved it but Im stuck where it says fill the array with only unique numbers , meaning A number cannot be repeated inside the array ..

here is the question :

Write a program that uses a random number generator to fill an array with 30 unique numbers between 0 and 100. The program prints out the array and then prints out all even numbers larger than the largest odd number in the array.

and here is my code :

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;
int i;
int array[30];
int odd;
int Max;
int counter = 0;


int main()

{	
	cout << "The array consist of 30 elemnts is: ";
	cout << endl;

	srand ( time(0) );

	for (int j = 0;j<30;j++)
	{

		i = rand() % 101;
		 

		 if (i != i-1)
			array[j]=i;

		 else
		 {
			i = rand() % 101;
		 array[j]=i;
		 }
	}
	
	for (int k = 0; k < 30 ; k++)
	{
		cout << array[k] << " ";

	}
	cout << endl;
	
	cout << "All the even numbers larger than the largest odd number are: ";
	for (int l = 0; l < 30 ; l++)
	{
		odd = -1;
		Max = -1;
		for (int n = 0; n < 30 ; n++)
		{
			if (array[n] % 2 != 0 && array[n] > Max)
				{
					odd = array[n];
					Max = array[n];
				}
		}

		
		
	}
	
	for(int u = Max+1;u<=100;u++)

		{
			if (u % 2 == 0)
				cout << u << " ";
			if (u == 100)
				break;
		}
	cout << endl;
	cout << "The largest odd number is : " << Max;
	cout << endl;
	return 0;
}

[Alterah]

You'll need to check the newly generated number against the numbers in the array. The easy way to do this is to have a function that does it for you. You can then check this inside of the for loop. Basically, if you find the number in the array, then you need to generate a new random number.

[nuzzle]

As an alternative approach you could declare an array with 101 boolean elements. Initially you set all elements to false. Then you start generating random numbers and if the corresponding index position in the array is false you change it to true and increment a counter (which initially is set to zero). If an array element already is true you just continue with the next random number because you know this random number has already been counted. When the counter reaches 30 you have 30 random numbers (it's the index positions with true elements).

Yet another approach is to use an array with 101 integer elements this time. Initially you fill the array with the integer sequence from 0, 1, 2, ... up to 100. You introduce a counter representing the number of remaining array elements. Initially it's N=101. Then you generate a random index position within the N range. The integer at that position is the first random number. You store it in some other array. Since one random number now is taken you decrement N. Then you overwrite the taken random number with the last random number of the array (it's at index position N). Now you generate another random index position within the N range, etcetera. This goes on until you have extracted 30 random numbers.

The first is a variation of the set approach to unique random number generation and the second is a variation of the random shuffle approach.

[EnGxSoLiD]

I think I solved it thanks to you guys

I actually used a recursive function

here is the new code

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;
int i;
int array[30];
int odd;
int Max;
int counter = 0;



int unique(int array[] , int l)
{
	int s;

	if (array[l] == 0)
	{
		array[l]=i;

	return array[l];
	}
	else
	{
		s=l-1;
		if (i == array[s])
		unique(array,s);
		return 0;
	}
}

int main()

{	
	cout << "The array consist of 30 elemnts is: ";
	cout << endl;

	srand ( time(0) );

	for (int j = 0;j<30;j++)
	{

		i = rand() &#37; 101;
		 
unique(array , j);
	}
	
	for (int k = 0; k < 30 ; k++)
	{
		cout << array[k] << " ";

	}
	cout << endl;
	
	cout << "All the even numbers larger than the largest odd number are: ";
	for (int l = 0; l < 30 ; l++)
	{
		odd = -1;
		Max = -1;
		for (int n = 0; n < 30 ; n++)
		{
			if (array[n] % 2 != 0 && array[n] > Max)
				{
					odd = array[n];
					Max = array[n];
				}
		}

		
		
	}
	
	for(int u = Max+1;u<=100;u++)

		{
			if (u % 2 == 0)
				cout << u << " ";
			if (u == 100)
				break;
		}
	cout << endl;
	cout << "The largest odd number is : " << Max;
	cout << endl;
	return 0;
}

[Paul McKenzie]

I think I solved it thanks to you guys

I actually used a recursive function

You don't need recursion. Use a container that only holds unique values to help you. In the example, items from the array are inserted into a set. At the same time, a check is made to see if the item is already in the set.

Since a set does a search in logarithmic time, it is much faster than going through an array in a linear fashion searching for duplicates.

#include <set>
#include <algorithm>
#include <iostream>
#include <ctime>

template <typename T>
bool isUnique(T *ptr, unsigned int numItems)
{
        std::set<T> ourSet;  
        for(unsigned int i = 0; i < numItems; ++i )
        {
            if (ourSet.find( *ptr ) != ourSet.end() )  
                   return false;  
            ourSet.insert( *ptr );  
        }
        return true;
}

int main()
{	
        int array[30];
	srand ( time(0) );
        std::fill(array, array + 30, rand() &#37; 101);

        if ( isUnique(array, 30) )
            std::cout << "Array has unique values";
        else
            std::cout << "Array does not have unique values";
}

I won't explain further, since this looks like a homework problem.

Regards,

Paul McKenzie

[GCDEF]

Yet another approach would be to create a 101 bye array and fill it with the values 0 - 100. Call the random_shuffle function, then copy the first 30 elements to your new array. I would assume that qualifies as a random number generator.

[Eri523]

And while we're talking of alternative STL-based implementations of the approaches proposed by nuzzle, here's another one:

Keep inserting random interegers in the range 0 to 100 into an std::set<int> until its size() reaches 30.

[Lindley]

You don't need recursion. Use a container that only holds unique values to help you. In the example, items from the array are inserted into a set. At the same time, a check is made to see if the item is already in the set.

Since a set does a search in logarithmic time, it is much faster than going through an array in a linear fashion searching for duplicates.

#include <set>
#include <algorithm>
#include <iostream>
#include <ctime>

template <typename T>
bool isUnique(T *ptr, unsigned int numItems)
{
        std::set<T> ourSet;  
        for(unsigned int i = 0; i < numItems; ++i )
        {
            if (ourSet.find( *ptr ) != ourSet.end() )  
                   return false;  
            ourSet.insert( *ptr );  
        }
        return true;
}

int main()
{	
        int array[30];
	srand ( time(0) );
        std::fill(array, array + 30, rand() &#37; 101);

        if ( isUnique(array, 30) )
            std::cout << "Array has unique values";
        else
            std::cout << "Array does not have unique values";
}

I won't explain further, since this looks like a homework problem.

Regards,

Paul McKenzie

Overkill. As Eri says, this is sufficient:

int main()
{
    std::set<int> vals;

    while (vals.size() < 30)
        vals.insert(rand() % 101);

    int array[30];
    std::copy(vals.begin(),vals.end(),array);
}

[monarch_dodra]

Overkill. As Eri says, this is sufficient:

int main()
{
    std::set<int> vals;

    while (vals.size() < 30)
        vals.insert(rand() % 101);

    int array[30];
    std::copy(vals.begin(),vals.end(),array);
}

And you can always add a random_shuffle to hide from the professor that you used an stl set. Teachers tend to not like it when you do things the smart way...

[Paul McKenzie]

Overkill. As Eri says, this is sufficient:

int main()
{
    std::set<int> vals;

    while (vals.size() < 30)
        vals.insert(rand() &#37; 101);

    int array[30];
    std::copy(vals.begin(),vals.end(),array);
}

I'm assuming that the OP wants to know if the array has unique values, but this of course is the better way to do things.

Regards,

Paul McKenzie

[nuzzle]

but this of course is the better way to do things.

But there's an even better way and that's to simply replace the std::set with an std::unordered_set. It gives a lower complexity because set accesses then becomes O(1) rather than O(logN). This is possible when there's no requirement the numbers must be sorted.

Still it's worth mentioning that the set approach performs very bad if the number of wanted numbers (here 30) is close or even equal to the number of available numbers (101). Then the performance slows down to a crawl because eventually almost every trial random number will be a duplicate and rejected. In that case the random shuffle approach is superior.

[bluecoder]

I think I solved it thanks to you guys

I actually used a recursive function

here is the new code

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;
int i;
int array[30];
int odd;
int Max;
int counter = 0;



int unique(int array[] , int l)
{
	int s;

	if (array[l] == 0)
	{
		array[l]=i;

	return array[l];
	}
	else
	{
		s=l-1;
		if (i == array[s])
		unique(array,s);
		return 0;
	}
}

int main()

{	
	cout << "The array consist of 30 elemnts is: ";
	cout << endl;

	srand ( time(0) );

	for (int j = 0;j<30;j++)
	{

		i = rand() % 101;
		 
unique(array , j);
	}
	
	for (int k = 0; k < 30 ; k++)
	{
		cout << array[k] << " ";

	}
	cout << endl;
	
	cout << "All the even numbers larger than the largest odd number are: ";
	for (int l = 0; l < 30 ; l++)
	{
		odd = -1;
		Max = -1;
		for (int n = 0; n < 30 ; n++)
		{
			if (array[n] % 2 != 0 && array[n] > Max)
				{
					odd = array[n];
					Max = array[n];
				}
		}

		
		
	}
	
	for(int u = Max+1;u<=100;u++)

		{
			if (u % 2 == 0)
				cout << u << " ";
			if (u == 100)
				break;
		}
	cout << endl;
	cout << "The largest odd number is : " << Max;
	cout << endl;
	return 0;
}

This is good function unique

[bluecoder]

This is good function unique ...thanks

[Philip Nicoletti]

To the OP : I think you need to do additional testing on your code in post # 4

(to make it easier, sort the numbers before printing them out).

[bluecoder]

why such complicated code...


for (int j = 0;j<30;j++)
{
i = rand() % 101;
if (i != i-1)
array[j]=i;
else
{
i = rand() % 101;
array[j]=i;
}
}