An integer is a multiple of three if and only if the sum of its digits are a multiple of 3.
In order to consider the digits to be deleted so that the sum of digits a multiple of three, the following information is sufficient:

• The number of digits whose remainder divided by \(3\) is \(0\)
• The number of digits whose remainder divided by \(3\) is \(1\)
• The number of digits whose remainder divided by \(3\) is \(2\)

With this information, let us divide into cases:

• If the remainder of sum of all digits by \(3\) is \(0\) In such case, \(N\) is already a multiple of \(3\), so the answer is \(0\).
• If the remainder of sum of all digits by \(3\) is \(1\) In such case, we need to erase at least one digit.
  • If there is a digit whose remainder by \(3\) is \(1\) It is sufficient to erase that digit, so the answer is \(1\). Note that however, if \(N\) was originally a one-digit integer, since we are unable to erase all digits, so the answer is \(-1\).
  • Otherwise Since each digit’s remainder by \(3\) is either \(0\) or \(2\), there must be at least two digits whose remainder by \(3\) is \(2\). We can erase such two digits, so the answer is \(2\). Note that however, if \(N\) was originally a two-digit integer, since we are enable to erase all digits, so the answer is \(-1\).
• If the remainder of sum of all digits by \(3\) is \(2\) It is the same as the previous case
  • If there is a digit whose remainder by \(3\) is \(1\) It is sufficient to erase that digit, so the answer is \(1\). Note that however, if \(N\) was originally a one-digit integer, since we are unable to erase all digits, so the answer is \(-1\).
  • Otherwise Since each digit’s remainder by \(3\) is either \(0\) or \(1\), there must be at least two digits whose remainder by \(3\) is \(1\). We can erase such two digits, so the answer is \(2\). Note that however, if \(N\) was originally a two-digit integer, since we are enable to erase all digits, so the answer is \(-1\).

The number of total digits, or digits whose remainder by \(3\) is \(0\), can be obtained by converting \(N\) in decimal form. One can find the decimal form of \(N\) by repeating “record the remainder of \(N\) by \(10\), and divide \(N\) by \(10\), with the fraction rounded down.” The total time complexity is \(O(N)\). In order to handle with large integers like \(10^{18}\) in C or C++, one need to use integer types with (more than) 64-bit capacity, such as int64_t or long long Also, it is possible to solve this problem by exhaustively trying all the combinations of digits to erase, using binary integers, which requires a total of \(O(N^ {\frac{\log(2)}{\log(10)}} \log(N)) \) time.

Sample Code ©

#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;
}