UVA 10474 - “Where is the marble?”

I have been solving the problem from UVA 10474. In this problem, there will be marbles with numbers written on them. For example suppose five marbles with numbers 50 , 43, 43, 43, 2, 90, 44. There will be several query with number and position has to be told in a sorted sequence. For example after sorting these looks like : 2,43,43,43,44,50,90. Now, query for 43 will give output : 43 fond at 2 and query for -3 will output "-3 not found".

Can you please review it and provide me with feedback?

#include 
#include
#include
#include

void printMarbelPositionIfFound()
{
    int numMarbles, numQueries, aMarble, case1;
    std::vectormarbles;

    case1 = 0;

    while(true)
    {
        scanf("%d %d", &numMarbles, &numQueries);
        if(0 == numMarbles && 0 == numQueries)return;

        case1++;

        for(int i=0; i::const_iterator itr = std::lower_bound(marbles.begin(), marbles.end(),aMarble);
            if(*itr == aMarble)
            {
                std::cout<<aMarble<<" found at "<<itr - marbles.begin() + 1<<'\n';
            }
            else
            {
                std::cout<<aMarble<<" not found"<<'\n';
            }
        }

        marbles.clear();
    }
}

int main()
{
    printMarbelPositionIfFound();
    return 0;
}

You are mixing C with C++. I know these contests like speed, but it is usually unnecessary.

1. Prefer streams over scanf.

This means you can change this code:

scanf("%d %d", &numMarbles, &numQueries);

Into this:

std::cin >> numMarbles >> numQueries ;

1. Use the C++11 auto keyword when possible.

You have a C++11 tag, so I assume you have C++11 available.

You can change this:

std::vector::const_iterator itr = std::lower_bound(marbles.begin(), marbles.end(),aMarble);

To this:

auto itr = std::lower_bound(marbles.begin(), marbles.end(),aMarble);

1. Make sure the iterator does not point past the end when you dereference it.

In this line: if(*itr == aMarble), you dereference the iterator. If aMarble is not in marbles, then std::lower_bound() will return marbles.end(). It is undefined behavior to dereference marbles.end(). Always check for this condition.

So change this line:

if(*itr == aMarble)

To this:

if (iter != marbles.end () && *itr == aMarble)

1. Prefer pre-increment over post-increment.

You have:

case1++;

In the case an int, it doesn't really matter. Your compiler will optimize this correctly. But if you had a complicated object, then you would be creating an unnecessary copy here. So:

++case1;

Would be a better habit to get into.

1. Encapsulate input and output with an Object.

You could create an object that represents a single unit of input. Something like this:

struct Input
{
    int nMarbles ;
    int nQueries ;
    static int caseNumber ;

    std::vector  marbles ;
    std::vector  queries ;

    Input () ;
    void Clear () ;

    friend auto operator>> (std::istream &is, Input &input) -> std::istream& ;
    friend auto operator std::ostream& ;
};

Then you could implement the member and friend functions like this:

int Input::caseNumber = 0 ;

Input::Input () : nMarbles (), nQueries ()
{
} 

void Input::Clear ()
{
    nMarbles = 0 ;
    nQueries = 0 ;
    marbles.clear () ;
    queries.clear () ;
}

auto operator>> (std::istream& is, Input &input) -> std::istream&
{
    ++Input::caseNumber ;

    is >> input.nMarbles >> input.nQueries ;
        
    if (input.nMarbles == 0 && input.nQueries == 0) {
        is.setstate (std::ios::failbit) ;
        return is ;
    }

    auto begin = std::istream_iterator  (is) ;
    std::copy_n (begin, input.nMarbles, std::back_inserter (input.marbles)) ;
    
    begin = std::istream_iterator  (is) ;
    std::copy_n (begin, input.nQueries, std::back_inserter (input.queries)) ;

    return is ;
}

auto operator std::ostream&
{
    os << "CASE# " << Input::caseNumber << ":" "\n" ;

    auto &marbles = input.marbles ;

    std::sort (std::begin (marbles), std::end (marbles)) ;
    
    for (int query : input.queries) {
        auto iter = std::lower_bound (std::begin (marbles), std::end (marbles), query) ;

        if (iter != std::end (marbles) && *iter == query) {
            os << query << " found at " << (std::distance (std::begin (marbles), iter) + 1) << "\n" ;
        }

        else {
            os << query << " not found" "\n" ;
        }
    }

    return os ;
}

Then your driver would look like this:

int main ()
{
    Input input ;

    while (std::cin >> input) {
        std::cout << input ;
        input.Clear () ;
    }

    return 0 ;
}

With the above code, I got an accepted answer with a runtime of 0.212 units on your website. So streams are more than fast enough for this particular challenge.

StackExchange Code Review Q#73397, answer score: 4