Rubrik OA Question With Explainations

Round 1

Questions: At Rubrik, you are tasked with optimizing data compression in a distributed backup system. Each block of data is uniquely indexed by integers L to R, and your team uses a unique compression algorithm that combines blocks using bitwise AND operations. This ensures efficient deduplication, but calculating the total compressed size is computationally challenging for large datasets. Your mission is to compute the sum of bitwise AND results for all combinations of blocks within the given range L to R. The final result will help Rubrik fine-tune their storage optimization system. Since the result can be enormous, your team requires the sum modulo 10^9 + 7.

You are given T test cases. For each test case, compute the sum:

S = L + (L&L+1) + (L&L+1&L+2) + ... + (L&...&R)

where & denotes the bitwise AND operation. Return the result modulo 10^9 + 7.

First Try yourself