Two methods of solving the problem are provided here.
Program is written in Python and takes O(n) time.