# Tag Info

Given a non-negative integer $x$, let $|x|$ denote the number of ones in the binary representation of $x$. You can prove the claim by induction on $n$. The base case $n=0$ is trivially true. Consider then $n>0$. During the first iteration, the algorithm prints $n$ stars. The number $x$ of stars printed by the other iterations is exactly the number of ...