Your code is giving wrong output in this problem. Please refer the following code for correct output - https://ideone.com/4YIgmT