Here is one of the solutions of given question.
Still can be optimised, will brush these topics for sure
https://repl.it/@AdhityanK/GCInterviewDeepak