Rubrik OA Question - November 2024 With Explainations

 

Rubrik OA Problem: Range AND Challenge

Story:

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.

Problem Statement:

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.

Problem Breakdown:

1. Understanding the Range: The sum involves computing:

   $$$$S=(L)+(L&(L+1))+(L&(L+1)&(L+2))+⋯+(L&…&R)

   At each step, you perform a cumulative bitwise AND operation starting from $L$ up to $R$.

2. Optimization Insight:

   • The bitwise AND operation tends to reduce the number of 1 bits as you include more numbers in the range.
   • For a specific bit position (or column in binary representation), the result will flip to 0 when the pattern in that bit position reaches a point where all values in the range are 0 for that bit.
   • We can leverage this pattern to quickly compute contributions to $S$.

3. Key Idea: Column-Wise Calculation: For each bit column (from the least significant bit to the most significant bit), calculate how many consecutive numbers (from $L$) will have a 1 at that bit. Once the bit flips to 0, the contribution for that column stops.

Efficient Calculation:

1. Binary Representation Analysis:

   • In binary, each bit position alternates between blocks of 0 and 1.
   • For a given $L$, find its position in the block pattern of that bit.
   • Using this pattern, calculate how far L$\mathrm{can\; go\; before\; the\; AND\; result\; for\; that\; column\; becomes\; 0.}$

2. Steps:

   • Convert $L$ and $R$ to binary.
   • For each bit position $i$:
     1. Check if the $i$-th bit of $L$ is 1.
     2. If it is, calculate the block size of consecutive 1's for that bit position.
     3. Determine how many numbers from $L$ (up to $R$) fall in this block.
   • Add the contributions for each bit position to get $S$.

3. Block Calculation in $O(1)$:

• Each bit position alternates in blocks of $2^i$.
• Find the start and end of the block where $L$ falls for a given bit.
• Using modular arithmetic, calculate the length of the block where the bit remains 1.

CODE:

package bitmanipulation;

import java.util.Scanner;

public class RubrikOA {

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc=new Scanner(System.in);

long L=sc.nextLong();

long R=sc.nextLong();

long result=0;

for(int bit=0;bit<64;bit++) {

//check if the current bit in L is 1.

if((L & (1L << bit))!=0) {

//find the size of block..

long block=1L << bit;

//determine the range of numbers with the current bit is still 1.

long start=(L/block)*block;

long end=Math.min(start + block - 1, R);

if (start <= R) {

                    result += (end - L + 1) * (1L << bit);

                }

}

}

long MOD=(long)1e9;

System.out.println(result%MOD);

sc.close();

}

}

If you have any doubt feel free to comment down 👇