Republic Day Parade (Solution)
Published in
Jan 20, 2021
In this blog, we will look at how you could approach the problem “Republic Day Parade” in The Coding Culture’s January Contest “Bit by Bit”.
Approach:
Let us define function f(L, R), that gives answer to the query. It looks as follows:
Case L=R :
=> f(L, R) = L ;
Case 2^b ≤ L, where b — maximum integer such that 2^b ≤ R:
=> f(L, R) = f( L -(2^b), R - (2^b) ) + (2^b) ;
Case 2^(b + 1)–1 ≤ R :
=> f(L, R) = 2^(b + 1)-1 ;
Otherwise :
=> f(L, R) = (2^b) - 1.
Solution:
Time Complexity:
Total complexity is O( log(R) ) per query.
