2
\$\begingroup\$

Hear this problem: Write a C/C++ program that reads all the values from the "BAC.TXT" file and determines which are the two largest three digit numbers that are missing from the file using a time-efficient algorithm. This is the code that I wrote and it returned good values for all the input sets I tried:

#include <iostream>
#include <fstream>

using namespace std;

int main()

{   ifstream in("BAC.TXT");

    unsigned int a[1000], missing_numbers[2];
    unsigned int data, i = 0, j = 0, found_missing_numbers = 0;

    while(!in.eof())
    {   in >> data;

        if (data >= 100 && data <= 999)
            a[data] = 1;    
    }

    for(i=999;i>=100;i--)
    {if(a[i]!=1)
    {   missing_numbers[j] = i;
        found_missing_numbers++;
        j++;
    }
    if (found_missing_numbers == 2)
        break;
    }

    if (found_missing_numbers == 2)
    {
        cout << "The two largest numbers of three digits that are missing from the file are:";
        cout << missing_numbers[0] << " and " << missing_numbers[1];
    }
    else if (found_missing_numbers == 1)
        cout << "Only one three digit number is missing from the file:" << missing_numbers[0];
    else
        cout << "There are no three digit numbers missing from the file.";

    cin.get();

    in.close();

    return 0;
}

Example of Input:

125 88556 2534 12 456668 12 56324 4521 3 652 999 94 24521 6524 1112 125 997 12315 122 54 9 5546 754 998 12312 12152 745 2354 856 124 956 125 88556 2534 12 456668 12 56324 4521 3 652 999 94 24521 6524 1112 125 997 12315 122 54 9 5546 754 998 12312 12152 745 2354 856 124 956 125 88556 2534 12 456668 12 56324 4521 3 652 999 94 24521 6524 1112 125 997 12315 122 54 9 5546 754 998 12312 12152 745 2354 856 124 956 125 88556 2534 12 456668 12 56324 4521 3 652 999 94 24521 6524 1112 125 997 12315 122 54 9 5546 754 998 12312 12152 745 2354 856 124 956 125 88556 2534 12 456668 12 56324 4521 3 652 999 94 24521 6524 1112 125 997 12315 122 54 9 5546 754 998 12312 12152 745 2354 856 124 956 125 88556 2534 12 456668 12 56324 4521 3 652 999 94 24521 6524 1112 125 997 12315 122 54 9 5546 754 998 12312 12152 745 2354 856 124 956 125 88556 2534 12 456668 12 56324 4521 3 652 999 94 24521 6524 1112 125 997 12315 122 54 9 5546 754 998 12312 12152 745 2354 856 124 956 125 88556 2534 12 456668 12 56324 4521 3 652 999 94 24521 6524 11

Output:

The two largest numbers of three digits that are missing from the file are:996 and 995

I consider the code quite efficient because the file is read a single time and it selects and works only with the data that could help to find the solution. I would like to hear your opinion, other suggestions, all that you consider that could make this solution more efficient.

P.S. I am a beginner in programming, don't know any OOP for the moment. I know the code I wrote is something like C with cout and cin...not C++. Don't kill me. This question is based on the same problem that I was solving here, but now I have a working solution. Now it's only a matter of optimisation.

\$\endgroup\$
  • 1
    \$\begingroup\$ To clarify, this is C++, but it is very C-like, is that correct? \$\endgroup\$ – Phrancis May 13 '16 at 14:52
  • 1
    \$\begingroup\$ I don't see how this code could be considered valid C. It's definitely C++. \$\endgroup\$ – 200_success May 13 '16 at 14:57
  • \$\begingroup\$ I said this because I had a lot of comments for other questions in which other viewers told me to decide if I'm using C or C++. \$\endgroup\$ – CCBet May 13 '16 at 14:58
  • \$\begingroup\$ @Phrancis something like that .. \$\endgroup\$ – CCBet May 15 '16 at 18:05
4
\$\begingroup\$

Reading input

In this specific case it doesn't make a difference, but try to break the habit of using code like:

while (!some_file.eof())

Under most circumstances this leads to incorrect behavior--in particular, it will typically result in processing the last item in the file twice. In this code, we're just setting a value in an array to 1, so setting it to 1 again doesn't change anything, and the bug is hidden. Still better to avoid it.

while(in >> data)
{   
    if (data >= 100 && data <= 999)
        a[data] = 1;    
}

indentation

I'm a lot less than excited about your formatting, putting the first statement in a block on the same line as the block's opening brace:

while(!in.eof())
{   in >> data;

...

for(i=999;i>=100;i--)
    {if(a[i]!=1)

The usual advice is to pick a style and use it consistently. I'd add one item to that though: unless you have a really good reason to do otherwise, pick one of the styles that's already reasonably well know and widely used (e.g., K&R, OTBS, etc.)

Standard containers

Right now, your a is basically acting as a set. That it, it simply records what numbers are present/absent in a range. The standard library already provides std::set (and std::unordered_set, though it's probably not the best choice here) specifically for that purpose. It might be worth at least considering using one of these.

Simplification

Since we care about the numbers that are missing (rather than the ones that are present), we probably want to invert the sense of our set. Rather than inserting numbers as we encounter them, then searching for what's missing, we can start by inserting all the numbers from 100 to 999, then remove the numbers as we read them from the file.

This way, when we're done reading the data from the file, our set contains exactly what we care about: the numbers in the specified range that were not present in the file (if any).

Note that this can be a little bit of a tradeoff. If we expect a lot of numbers to be missing, we could be adding a fair amount of extra work by inserting all the numbers to start with, then removing them as we read. In a case like this, with only ~900 items in the range, that's probably irrelevant though--inserting 900 items in a set is fast enough that it usually won't matter nearly as much as simplifying the code can/does.

Standard algorithms

We can also use standard algorithms to ease the job a bit, such as using std::copy_n to copy the last two items in the set to std::cout, assuming we find two or more missing numbers.

Use of braces

A fair number of people advise using braces around the statement(s) controlled by every if, while, for, etc. Personally I don't like (or usually follow) this advice, but it's pretty widespread, and if you decide to do otherwise, you should (IMO) be consistent about whether to do it or not.

Summary

Code incorporating all these could look something like this:

std::set<int> s;

for (int i = 100; i < 1000; i++)
    s.insert(s.end(), i);

int data;

while (in >> data)
    s.erase(data);

if (s.empty())
    std::cout << "All numbers were present\n";
else if (s.size() == 1)
    std::cout << "The one missing number was: " << *s.begin() << "\n";
else {
    std::cout << "The two largest missing numbers were: ";
    std::copy_n(s.rbegin(), 2, std::ostream_iterator<int>(std::cout, " "));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.