string - 删除尽可能少的数字以使数字可以被 3 整除

Question

我正在解决这个问题，即我们给了数字 N，它可以很大，最多可以有 100000 个数字。

现在我想知道找到这些数字的最有效方法是什么，我认为在大数字中我最多需要删除 3 位数字才能被 3 整除。

我知道如果数字的总和能被三整除，我就知道这个数能被三整除，但我想不出我们该如何使用它。

我的想法是对字符串进行暴力破解，并检查我们是否删除了该数字是否可以被 3 整除，但我的解决方案在复杂示例中失败了。请给我一些提示。

提前致谢。

Answer 1

如果数字之和模 3 等于 1，则要删除单个 1、4 或 7。如果数字之和为 2，则要删除单个 2、5 或 8 .

如果做不到，则必须删除两位数。

为了避免扫描列表两次，您可以记住最多两位数与 1 一致的索引，以及最多两位数与 2 一致的索引，因此当您计算最终模数时，您知道在哪里看。