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 开始迭代并检查每个小数点是否可以将数组分成三等份。

是否有任何有效的算法。

Answer 1

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