I'm having the same problem and I have enough space for the game. The only other problem I could think of is if the game only works and newer versions of android
I have a pretty old phone and it's working there. Dunno what the problem could be, because, yes, it's a case by case when it comes to android be side of different structures, but generally speaking, it should work in any device as long as you have at least 800mb of space.