How to come up with counterexamples for an approach.
I get the logic and I am pretty sure that this approach would work until I get to know the case where it would fail.
Only if I could come up with edge cases quickly it would help me avoid coding wrong answers and then changing the logic and coding again.
Has someone faced a similar problem and does anyone have any good tips for this?
Thank you!
May the compiler be with you.
I am facing similar issues in greedy and dynamic programming problems :\
Create your own testcases with a generator and test your program with asserts. Or first create a brute force version which always gives correct output, then make an optimized program and compare the cases in which your optimized program differs from the correct brute-force one.
An example (by errichto): https://www.youtube.com/watch?v=JXTVOyQpSGM.
This is on Linux but I’m sure you can find something similar for windows. If you’re using sublime, there are lots of such plugins you can find.
Tip: One thing which has worked for me was to try to think of cases that your current approach won’t consider. For example, if your algorithm chooses first smallest element to the left of index ‘i’ in a sub step, then try to prove that this approach holds true to arrive at the solution rather than proceeding with the solution.