Competitive Programming Solutions

abc182_c - To 3

23 Jan 2021 — Tags: implementation,math — URL

Observations:

  1. For a number to be divisible by $3$ the sum of its digits must be divisible by $3$.
  2. Removing two digits with the same remainder $r$ is equivalent to removing remainder $3 - r$ from the overall digit sum.

Say that a number $x$ has a digit sum equal to $s$ and $s$ has remainder $r$ when divided by $3$. Let’s handle some of the cases.

If $r$ is zero, then we’re done.

If there’s a digit with remainder $r$ in $x$, we remove it and we’re done.

If there are two digits remainder $3 - r$, we remove then and we’re done.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int solve(vi a)
{
    int n = (int)(a).size();
    vi rem(3, 0);
    for (auto ai : a)
        rem[ai % 3]++;
    int sum = accumulate(begin(a), end(a), 0);
    if (sum % 3 == 0)
        return 0;
    if (n > 1 and rem[sum % 3])
        return 1;
    if (n > 2 and rem[3 - (sum % 3)] >= 2)
        return 2;
    return -1;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    string n;
    cin >> n;
    vi a(n.size());
    transform(begin(n), end(n), begin(a), [](char c) { return c - '0'; });
    cout << solve(a) << endl;
    return 0;
}

Related posts