Translation:My new girlfriend does not have a cat.
Yeah, this is not good English. The only time you'd use this construction is either for uncountable things (I have no beer) or for a thing you'd only have one of (I have no mother, I have no job). The course needs to be much more flexible about allowing normal English phrasing through when the direct translation is a mismatch.
LeviKane1 is completely and totally wrong. It's not normal, it's not usual - rather, it's weird. If you were going to use Duo's format, you'd say, "My new girlfriend has no cats", but even that is odd.
"Having no cat" puts the sentence into the abstract, rather than the concrete, and the sentence is not about an abstraction.
"doesn't have a cat/any cats" is the idiomatic English way of expressing this sentence.
In nominative, «ко́шки» or «коты́». In this sentence, «У мое́й но́вой де́вушки нет ко́шек/кото́в».
“My new girlfriend has no cats” is probably more common phrasing than “My new girlfriend has no cat” when you want to talk about her pet ownership in general. However, neither is more syntactically natural than the other. I could see saying either depending on what I wanted to stress - that she owns absolutely no cats, or my incredulity that someone would think she owns a cat.
But if I wanted to say she had no single feline pet, I’d still just say, “My new girlfriend does not have a cat.” All are still valid.
I wonder if you are thinking of some adjectives which, in their masculine form, end in -ой. Example, большой. If so, keep in mind that adjectives which end in -ой in the masculine form are stressed on the ending (on the o), and then when declined, that stress never changes placement. Contrast that adjectives which end in -ий, -ый are not stressed on the ending.
So the masculine form of new is not новой but новый. All stress will always fall on the first syllable in новый's declensions - have a look at that table in the link, and you will see this. Compare to the stress in the table of declensions for большой. Hope this helps.