Photo by Cookie the Pom on Unsplash

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.

--

--