Republic Day Parade (Solution)
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”.
Contest Page | CodeChef
CodeChef - A Platform for Aspiring Programmers CodeChef was created as a platform to help programmers make it big in…
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 ;
=> f(L, R) = (2^b) - 1.
Total complexity is O( log(R) ) per query.