Simple-Enough problem

#1

Anyone, Please let me know what is time complexity for my approach to this problem.

Solution Link-https://ide.codingblocks.com/s/65791

#2

you are doing string concatenation and this operation is O(n).
Here in your code, Height= log(n) as you are doing n/2 and at every node you are concatenating that is O(n).
So total complexity is O(n log n) roughly.
Bt check constraint on n
0 ≤ n < 10^12
So O(n logn) will not work.
You need to solve it in O(log n) roughly.
Refer my code : it is more optimized bt could be little tricky for u to understand
https://ide.codingblocks.com/s/65844
func -> gives me size of final string
func2-> only goes in recursion where string length is in between l and r and c1 is counting 1 bit

Hit like if u get it :slight_smile:

2 Likes
#3

Thankyou, Sir Crystal Clear. Got it.