正の整数が \(3\) の倍数であることと、その数のすべての桁の和が \(3\) の倍数であることは同値です。
すべての桁の和を \(3\) の倍数にするために消す桁 を考えるにあたって以下の情報だけあれば十分です。

• \(3\) で割った余りが \(0\) の桁の数
• \(3\) で割った余りが \(1\) の桁の数
• \(3\) で割った余りが \(2\) の桁の数

これを踏まえたうえで場合分けをします。

• すべての桁の和を \(3\) で割った余りが \(0\) の場合
  この場合既に \(N\) は\(3\) の倍数なので答えは \(0\) です。
• すべての桁の和を \(3\) で割った余りが \(1\) の場合
  この場合少なくとも \(1\) つ桁を消さないといけません。
  • \(3\) で割った余りが \(1\) の桁が存在する場合
    その桁を消せばよいので答えは \(1\) です。ただし\(N\) が元々 \(1\) 桁だった場合全ての桁を消すことになってしまうので答えは \(-1\) です。
  • そうでない場合
    \(3\) で割った余りが \(0\) 又は \(2\) の桁だけから構成されるので \(3\) で割った余りが \(2\) の桁が \(2\) 個以上あるはずです。そのような桁を \(2\) つ消せばよいので答えは \(2\) です。ただし\(N\) が元々 \(2\) 桁だった場合全ての桁を消すことになってしまうので答えは \(-1\) です。
• すべての桁の和を \(3\) で割った余りが \(2\) の場合
  余りが \(1\) の場合と同様です
  
  • \(3\) で割った余りが \(2\) の桁が存在する場合
    その桁を消せばよいので答えは \(1\) です。ただし\(N\) が元々 \(1\) 桁だった場合全ての桁を消すことになってしまうので答えは \(-1\) です。
  • そうでない場合
    \(3\) で割った余りが \(0\) 又は \(1\) の桁だけから構成されるので \(3\) で割った余りが \(1\) の桁が \(2\) 個以上あるはずです。そのような桁を \(2\) つ消せばよいので答えは \(2\) です。ただし\(N\) が元々 \(2\) 桁だった場合全ての桁を消すことになってしまうので答えは \(-1\) です。

\(N\) の桁数や、\(3\) で割った余りが \(0\) の桁の数などは、\(N\) を \(10\) 進数展開すれば求められます。\(N\) が \(0\) になるまで、「\(N\) を \(10\) で割った余りを記録し、\(N\) を \(10\) で割る ( 切り捨て ) 」ということを繰り返すと\(10\) 進数展開できます。計算量は \(O(\log (N))\) です。
C や C++ で \(10^{18}\) といったような大きな数を扱うためには int64_t や long long などの 64 bit (以上) の幅を持つ整数型を使う必要があります。
他にも \(N\) が \(18\) 桁しかないので消す桁を \(2\) 進数を使って全探索するという \(O(N^ {\frac{\log(2)}{\log(10)}} \log(N)) \) 解法もあります。

解答例 (C)

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main() {
	int64_t n;
	scanf("%" SCNd64, &n);
	
	int cnt[3] = { 0 };
	while (n) {
		cnt[n % 10 % 3]++;
		n /= 10;
	}
	int cur = (cnt[1] + 2 * cnt[2]) % 3;
	int k = cnt[0] + cnt[1] + cnt[2];
	int res;
	if (!cur) res = 0;
	else if (cur == 1) {
		if (cnt[1]) {
			if (k == 1) res = -1;
			else res = 1;
		} else {
			if (k == 2) res = -1;
			else res = 2;
		}
	} else {
		if (cnt[2]) {
			if (k == 1) res = -1;
			else res = 1;
		} else {
			if (k == 2) res = -1;
			else res = 2;
		}
	}
	printf("%d\n", res);
	
	return 0;
}