synch the contacts on my Android with the current contacts on Google Contacts
Log out from your google account. 
Delete all contacts - make sure all contacts are deleted from all sources.
Log in to your google account


There is a auto - backup and restore option (Find more here). There is possibility that your device may restore the contacts that were deleted just before the formatting.