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.
