WOw I think this is the optimal solution!
Let me explain the core idea:
We traverse from right to left, before you met the next bit that is 0, you should met Even number of 1s!
The rest part after the next bit of 0 are always valid:)
And we have assumption that the input always has bits[n-1] = 0:)