Given N coins that look identical and should be the same weights. However, one is a fake coin, which is lighter than the others. Your task is to design algorithms (written in Python) to find the fake coin. For practical purposes, you can use the same procedure of generating coins regular coins having weights of 2 and the fake coin having weight of 1.
1. Design an iterative algorithm to find the fake coin.
2. Design a recursive algorithm to find the fake coin by dividing N coins in two groups and weight them.
3. Design a recursive algorithm to find the fake coin by dividing N coins in three groups and weight them.
4. Bonus points are given for submissions that contain test cases that show each submitted algorithm is correct.
These algorithms should be written in Python. Each of the three algorithms should be a separate function in Python.
