1
\$\begingroup\$

Task

Input - integer number (year)

Print one number - the next year, in which all digits are pairwise different, and there are no digits 2 and 0. If there will never be such a year, print -1.

My solution (correct)

Could you please recommend time / space complexity optimizations?

vector<char> toVec(int n) {
    vector<char> res;
    while (n > 0) {
        res.push_back((n % 10) + '0');
        n /= 10;
    }
    return res;
}

int main(){
    int year;
    cin >> year;
    for (int i = year + 1; i < pow(10, 8); ++i) {
        vector<char> v = toVec(i);
        if (find(begin(v), end(v), '2') == v.end() and
            find(begin(v), end(v), '0') == v.end()) {
            set<char> temp(v.begin(), v.end());
            if (v.size() == temp.size()) {
                cout << i;
                return 0;
            }
        }
    }
    cout << -1;
    
}
\$\endgroup\$
2
  • \$\begingroup\$ pow() is a floating-point function, and should generally avoid them when you can. More importantly, it gets called every iteration of the loop; you should probably precompute and store the result in a variable and use that variable in the loop. \$\endgroup\$
    – Ilkhd
    Commented Dec 23, 2020 at 20:50
  • \$\begingroup\$ @Ilkhd gcc actually optimizes i < pow(10, 8) to the equivalent of i < 100000000, but I agree you shouldn't rely on that. \$\endgroup\$
    – benrg
    Commented Dec 23, 2020 at 23:08

1 Answer 1

2
\$\begingroup\$

You seem to be missing some headers (<vector>, <iostream>, <cmath> and <set>), and also to be assuming the standard names are in the global namespace, rather than std.

After attempting to read from std::cin, it's important to ensure the read was successful before attempting to use the result. (E.g. if (!(std::cin >> year)) { std::cerr << "Input failure\n"; return EXIT_FAILURE; }).

A linear search will be inefficient, especially as we may have to skip long runs containing the banned digits 0 and 2. It would be better to construct the result using the available digits than to consider and test every possible number. The search is flawed anyway, since std::pow(10, 8) could be larger than the maximum int, leading to overflow (which is Undefined Behaviour).

\$\endgroup\$
2
  • \$\begingroup\$ On what kind of hardware is INT_MAX < 10^8 ? A mic microcontroller? ;-) Agree about composing from digits. \$\endgroup\$ Commented Dec 24, 2020 at 0:07
  • \$\begingroup\$ INT_MAX must be at least 32767, which is significantly less than 10⁸; I wouldn't want to enumerate all platforms, but certainly 8-bit microcontrollers are likely to tend towards the smaller values. \$\endgroup\$ Commented Dec 24, 2020 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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