C++ array excercise-help needed

Question

I'm C++ begginer. I did this excercise from Deitel's book:

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 it in the array only if it is not a duplicate of a number already read. After reading all the values, display only the unique values that the user entered. Provide for the "worst case" in which all 20 numbers are different. Use the smallest possible array to solve this problem.

Here is my code:

#include <iostream>

using namespace std;

bool compare(int arrayNum[],int arraySize,int element);

int main()
{
    const int size=20;
    int i=1;
    int num[size];
    int arrayElement;
    int counter=0;

    while(i<=20)
    {

        cin>>arrayElement;
        if(i==1)    //stores first element in array
            num[0]=arrayElement;
        //compare new element with stored elements
        //if element is not a duplicate store it in array
        else if (compare(num,size,arrayElement))
        {
            counter++;
            num[counter]=arrayElement;
        }


        i++;
    }
    //displays array elements
    for(int k=0;k<=counter;k++)
        cout<<num[k]<<endl;

    return 0;
}

//compare elements in array

bool compare(int arrayNum[],int arraySize,int element)
{
    for(int j=0;j<arraySize;j++)
    {
        if(arrayNum[j]==element)
            return false;
    }

    return true;
}

It works, but I'm not sure if I have interpreted the task correctly. I assume then I don't have to include conditional statement for range of numbers (10 to 100 inclusive), as this will be read from the keyboard and input by me. Therefore why was this instruction included? Also at the end it says

use the smallest possible array

I assume the max size has to be 20,but I don't think there is a way to dynamically expand array size (for example while storing new elements) as array size is const. I would appreciate if someone could help me with this. Any comments regarding code, or better solution are welcome.

Answer 1

I'm studying C++ in the same book!! My first implementation for solving this problem was one that don't use any complementar array.. it uses a linear search to find duplicates..

take a look:

#include <iostream>
using namespace std;

// remember: size_t = unsigned int
const size_t arraySize = 20;
size_t _array[ arraySize ];

// global variable to keep track of the last used
// position in the _array
size_t counter = 0;

// the argument is not changed, so pass it by
// const reference
bool dupSearch( const int & );

int main()
{
    // disregard this
    ios_base::sync_with_stdio( false );

    // "temp" variable declared outside the loop to
    // avoid repeated allocation and deallocation
    int i = arraySize, temp;

    // look at the loop condition below " ( i-- ) "
    // remember:
    // false = ( every expression evaluated to 0 )
    // true  = ( every expression evaluated to a non-zero result )
    // more details on pag. 108 of the book. 8/e Portability tip 4.1
    while ( i-- )
    {
        // read the number from the user
        cin >> temp;

        // if the number entered is valid, put the
        // number on _array[ counter ] and increment 'counter'
        if ( dupSearch( temp ))
        {
            _array[ counter ] = temp;
            ++counter;
        }
    }

    // print the result in column format
    cout << endl;
    for ( size_t j = 0; j < counter; ++j )
        cout << _array[ j ] << endl;
}

// validation: if the value is out of the described range, return false
// if is in the range, check for duplicates using linear search.
// if a duplicate is found, return false
// otherwise, return true.
bool dupSearch( const int &a )
{
    if ( a < 10 || a > 100 )
        return false;
    else
        for ( size_t i = 0; i < counter; ++i )
            if ( _array[ i ] == a )
                return false;

    return true;
}

the number of comparisons is
n = ( n * ( n + 1 )) / 2
where n = counter. worst case --> counter = 20 numbers --> loop 210 times through the program execution.

Answer 2

I assume then I don't have to include conditional statement for range of numbers (10 to 100 inclusive), as this will be read from the keyboard and input by me. Therefore why was this instruction included?

Sure, in this case you wrote the code and know to enter numbers within the range expected; however, it is a standard best-practice to always validate input data from a user, always. That way erroneous values are handled gracefully (with an appropriate error message) and helps to make your program more robust.

Also at the end it says

use the smallest possible array

I assume the max size has to be 20,,,

I think what they might have been getting at here is that you could have used an array of 91 bytes as shown below.

int cnt = 0;      // count of unique values entered
byte values[91];  // values entered indicator array
int valIdx;       // used as values array index

memset((void *)values, 0, sizeof(values));  // initialize array to all zeros

while ( cnt < 20 )
{
   // [code for the following comments not shown]
   //   have user input a number
   //   validate the number (>= 10 && <= 100) 
   //   subtract 10 from the number and store it in valIdx 
   //   (now valIdx will contain a number >= 0 <= 90)

   if ( !values[valIdx] )
   {
      values[valIdx] = 1;
      ++cnt;
   }
}

// then to show the unique values...

for ( valIdx = 0; valIdx < sizeof(values); valIdx++ )
{
   if ( values[valIdx] )
   {
      cout << valIdx + 10 << endl;
   }
}

That solution however, would not have met the "use the smallest array possible" requirement.

Back to your code...

I would go ahead and add the user input validation, just for completeness (and to get into the habit of never trusting users (especially yourself).

As far as improvements go, here is one thing to think about. The compare routine goes through every array element when a unique number has been entered. It only needs to check against those that have a stored value in them. Making that change should lead you to refactor the contents of your while loop as well.

Answer 3

As each number is read, validate it and store it in the array

Emphasis mine. The text clearly says that your program has to validate the input. In other words, it has to check that the entered number is between 10 and 100, and if it is not, handle the error appropriately. So yes, you do need a conditional, although exactly what you do to handle the error is up to you.

And you're right, since arrays aren't dynamically resizable, the array size has to be at least 20.

Answer 4

The smallest possible array is a char[12], where the individual bits are used as flags.

char data[12]; // memset(data, 0, sizeof(data)); in main();

void set(int n_raw;)
{
   int n = n_raw - 10;
   int index = n/8;
   int offset = n-8*index;
   data[index] |= 1 << offset; // added "1 <<"
}

Reading the values back is left as an exercise for the student.

Answer 5

You do need a conditional. Basically it's saying to take in a number between 10 and 100. If it's not a number between those ranges, don't store it. Also, if that number already exists in the array, don't store it. Then just print out the values in the array.

You assume correct about the array size, it's maximum size would be 20, although you may not store all 20 values (again, because some input might be bad).