Diviser le tableau binaire en trois parties de telle sorte que chaque partie représente la même valeur décimale.

Question

Étant donné un tableau binaire, diviser le tableau en trois parties de telle sorte que chaque partie représente la même décimale.

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

Le tableau ci-dessus peut être divisé de la manière suivante :

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

Une approche simple consisterait à itérer à partir de 1 et à vérifier que chaque décimale peut diviser le tableau en trois parties égales.

Existe-t-il un algorithme efficace pour cela ?

Answer 1

Compter le nombre de bits activés. Il n'y a pas de solution si ce nombre n'est pas divisible par trois. Disons qu'il l'est, et qu'il y a 3k bits de réglés. Trouvez les positions du premier, du k+1 et du 2k+1 set bits. Continuez à incrémenter les trois positions et à les comparer jusqu'à ce que vous atteigniez le dernier set bit ou que vous soyez en désaccord. Si vous arrivez au dernier bit de set et que les trois sont d'accord, vous avez une solution.