I might be missing something big, but isn&#x27;t chemical equation balancing just a system of linear Diophantine equations[1]? If it is, you should be able to solve it in O(n^3) time by converting to Smith normal form[2]. Unlike Hermite form, which the paper mentions, you don&#x27;t need rational arithmetic or floating points.<p>[1]<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Diophantine_equation#System_of_linear_Diophantine_equations" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Diophantine_equation#System_of...</a>
[2]<a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Smith_normal_form" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Smith_normal_form</a>