Given two integers x and y, you need to find the total number of good pairs of integers (a, b) such that l a, b r. Note that pairs (a, b) and (b, a) are considered different if a b (i.E the pairs are ordered).
Answers
Step-by-step explanation:
The above problem can be solved using bitmask DP.
Initialise a 4-D DP array of size 64×64×64×2 as 10^18 has a maximum of 64 set bits with -1
The first state of the DP array stores the number of bits traversed in C from right. The second state stores the number of set-bits used out of X and third state stores the number of set bits used out of Y. The fourth state is the carry bit which refers to the carry generated when we perform an addition operation.
The recurrence will have 4 possibilities. We start from the rightmost bit position.
If the bit position at C is 1, then there are four possibilities to get 1 at that index.
If the carry is 0, then we can use 1 bit out of X and 0 bit out of Y, or the vice-versa which generates no carry for next step.
If the carry is 1, then we can use 1 set bit’s from each which generates a carry for the next step else we use no set bits from X and Y which generates no carry.
If the bit position at C is 0, then there are four possibilities to get 0 at that bit position.
If the carry is 1, then we can use 1 set bit out of X and 0 bit out of Y or the vice versa which generates a carry of 1 for the next step.
If the carry is 0, then we can use 1 and 1 out of X and Y respectively, which generates a carry of 1 for next step. We can also use no set bits, which generates no carry for the next step.
Summation of all possibilites is stored in dp[third][seta][setb][carry] to avoid re-visiting same states.