algorithm - 将二进制数组分成三部分，使每一部分代表相同的十进制

Question

给定一个二进制数组，将数组分成三部分，使每一部分代表相同的十进制。

Eg arr[] = {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1}

上面的数组可以按以下方式划分：

{1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}, {1}. Now each part represent same decimal.

一种简单的方法是从 1 开始迭代并检查每个小数是否可以将数组分成三个相等的部分。

是否有任何有效的算法。

标签： algorithm

Answer 1

计算设置的位数。如果这个数字不能被三整除，则没有解决方案。说它是，并且有 3k 个设置位。找到第一个、k+1 和 2k+1 个设置位的位置。继续增加所有三个位置并进行比较，直到到达最后一个设置位或出现分歧。如果您在所有三个都同意的情况下到达最后一个设置位，那么您就有了解决方案。