For the above problem can we have o(n) solution as stated in one of the comments. I really have no idea how to do it in O(n) time complexity ,though i did it in O(n^2).