Competitive Programming Solutions

1465B - Fair Numbers

20 Dec 2020 — Tags: brute_force,observation — URL

Note that the minimum fair integer $x$ such that $n \leq x$ is at most $lcm(1, 2, …, 9)$ steps away ($2520$). This is the period of fair numbers that contain all single non-zero digits, therefore, the maximum period.

Brute force approach:

  • Test if number is fair, if not increment it and try again until it is.

Time complexity: $O(1)$

Memory complexity: $O(1)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool fair(ll n)
{
    ll x = n;
    while (x != 0)
    {
        int d = x % 10;
        if (d and n % d)
            return false;
        x /= 10;
    }
    return true;
}
ll solve(ll n)
{
    while (not fair(n))
        ++n;
    return n;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        cout << solve(n) << endl;
    }
    return 0;
}

Related posts