Germany
Usually paid toilets are cheap (.5-1 €) and clean. Free toilets are not always so clean.
You must see that public toilets are seldom used by the individual, usually one can serve such needs at home, at school, at work or at a restaurant, where it is usually free (for guests at restaurants). When one is in the (usually unexpected) need, then prefers cleanliness to freeness.