What to do about a virus that stayed even after a factory reset?

[AC Question]

Let me start off by saying that I've had this Samsung Galaxy Note 10.1 for a few years now, so my warranty is no longer valid.
A few weeks ago I noticed an app called "Game" had appeared in my home screen. The first thing I did, obviously, was go to the play store and check my apps to see if someone had downloaded it on my tablet, but I couldn't find that app in my downloaded apps. I then checked the Application Manager from settings, but I STILL couldn't find the app! I had absolutely no way to uninstall it!
I noticed that that app opens a a small pop-up that covers the bottom half of the tablet, and the pop-up is just an ad for various other apps. If I click on the ad it takes me to the play store page for the app that's advertised. This pop up doesn't necessarily get in my way or anything, since it only pops up a few times randomly throughout the day. No more than 10 times I'd say.
Back to what I was saying, I couldn't uninstall the app, so I naturally assumed it was a virus. Not a huge, bothersome virus, but still a virus, and I'm worried it might be collecting my information or something.
Since I had no other option, I tried doing a factory reset, but the virus was still there after the reset. I then did some more research on the internet, and then tried to do another reset, but only after I had encrypted the device, in hopes that it wouldn't be able to get through to my tablet again.
I don't know what to do anymore. A factory reset has always been my go-to solution whenever I have no other way of removing a virus from my laptop, but I guess it's different for android devices.
Please let me know if there's anything else I can try doing to remove the virus!

 

[Rukbat]

Reflash the ROM.

If that doesn't do it (and I can't see an app living through a reflash), learn a little Linux and use dd to write random to everything except the download partition. If the app survives that, intelligent software is here and no one told us. But I think a simple ROM reflash will do it. (Even encrypting and a factory reset won't remove a system app, and if the virus was installed as a system app ...)

See [Samsung] How to flash Stock ROM via ODIN if you don't know how to flash a Samsung.

 

[laphunhon]

Reason: factory reset will Create and Override some system app/file but not del orther file (which include virus app like as bloatware )
Solution : Use root del virus apk which will be install like as system app when booting.
+ Your sytem must be rooted
+ Del virus app normal way first.
+ Install ES File Explorer, go to Local->Home
=> tap / in address /local to move into root Directory
=> find address /system/app -> del file virus .apk then reboot

 

[kolly12]

I've gone throught my apps and can't locate a problem but I've had this virus now for over a year and it is eating my battery it makes my battery super hot and it pops up telling me I have 4 critical viruses destroying my battery I have gone through 3 batteries in the last year factory reset will not remove it. I have the galaxy s 3

 

[AlphaTango414]

Reflash your stock firmware.