Lost all contacts

[Dusty-Mouse]

I changed providers and they issued me a new number in error. Now my contacts have gone. What can I do to get them back? It is an Android phone

 

[Titillating]

Were your contacts synced to any apps or cloud-based services? Or maybe they were backed up to your SIM card (if you have one)?