It has recently been shown that turbulence in the interstellar medium (ISM) can significantly accelerate the growth of dust grains by accretion of molecules, but the turbulent gas-density distribution also plays a crucial role in shaping the grain-size distribution. The growth velocity, i.e., the rate of change of the mean grain radius, is proportional to the local gas density if the growth species (molecules) are well-mixed in the gas. As a consequence, grain growth happens at vastly different rates in different locations, since the gas-density distribution of the ISM shows a considerable variance. Here, it is shown that grain-size distribution (GSD) rapidly becomes a reflection of the gas-density distribution, irrespective of the shape of the initial GSD. This result is obtained by modelling ISM turbulence as a Markov process, which in the special case of an Ornstein-Uhlenbeck process leads to a lognormal gas-density distribution, consistent with numerical simulations of isothermal compressible turbulence. This yields an approximately lognormal GSD; the sizes of dust grains in cold ISM clouds may thus not follow the commonly adopted power-law GSD with index -3.5, but corroborates the use of a log-nomral GSD for large grains, suggested by several studies. It is also concluded that the very wide range of gas densities obtained in the high Mach-number turbulence of molecular clouds must allow formation of a tail of very large grains reaching radii of several microns.