The Coding Culture
Published in

The Coding Culture

Photo by Cookie the Pom on Unsplash

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”.

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store