$$$90 = 9 \times 10$$$. So a number will be divisible by $$$90$$$ if and only if it's divisible by $$$9$$$ and $$$10$$$.

A number will be divisible by $$$10$$$ if it has a trailing $$$0$$$. A number will be divisible by $$$9$$$, if the sum of it's digits are divisible by $$$9$$$.

After taking input, count the number of $$$5$$$'s (we denote it by $$$f$$$). The number of $$$0$$$'s will be then $$$z = n - f$$$.

Remember we need the number to be divisible by both $$$9$$$ and $$$10$$$. So if $$$f = n$$$ (or $$$z = n - f = 0$$$), then there is no solution. Print $$$-1$$$.

At this point we know, there is at least one $$$0$$$. So we can construct a number that is divisible by $$$10$$$. The other condition was that the number has to divisible by $$$9$$$. Although the $$$0$$$'s sum up to $$$0$$$ and $$$0$$$ is divisible by $$$9$$$, we can't place leading $$$0$$$'s. So in order to satisfy the divisibility by $$$9$$$ constraint, we have to place a number of $$$5$$$'s to the left of $$$0$$$(or $$$0$$$'s) such that the number of $$$5$$$'s sum up to a number that's divisible by $$$9$$$.

How many $$$5$$$'s are needed to make the sum of $$$5$$$'s divisible by $$$9$$$? Notice that $$$\text{lcm}(5, 9) = 45$$$. So we need at least $$$9$$$ $$$5$$$'s to make the sum of digits divisible by $$$9$$$. In other words, let $$$f^\prime$$$ be the number of $$$5$$$'s that sum up to a number that's divisible by $$$9$$$. Then $$$f^\prime$$$ has to be a multiple of $$$9$$$. We have already counter the number of $$$5$$$'s (denoted by $$$f$$$). So we have to find the multiple of $$$9$$$ that is closest to $$$f$$$. We can find it by, $$$f^\prime = \lfloor \frac{f}{9} \rfloor \times 9 $$$. Think about as to why it's true.

We place $$$f^\prime$$$ number of $$$5$$$'s at the start. Now are we done? Almost. We already have a trailing $$$0$$$ and a bunch of $$$5$$$'s to its left. To make the number as large as possible, we place the remaining $$$0$$$'s (if there are any), between the $$$5$$$'s and the trailing $$$0$$$.

Submission: 90701750