Method overloading vs factory

Lets say we need some logic change in multiple methods of multiple classes on basis of a flag, while keeping backwards compatibility.

There are two ways..

1.overload every method in every class. then end up with an if-else ladder in caller code to call correct method.

2.Make a common interface and a Factory. Return objects of either on basis of flag passed to factory. Callers don't need any change. only a little change is needed while object creation. Is it logical to create factory for two types only ?

Based on your experience which will you choose ? How to decide between these two ways ? Any better approach you can suggest ?