Last Updated: 25 Sep, 2021

Optimize The Code

Moderate

Asked in companies

Solve now

Problem statement

While practicing questions on data structures, Ninja faced a problem and was not able to pass all the test cases of a question as the time complexity of the code Ninja made was very large. Ninja asked you for help. You are given a snippet of code and you have to optimize the code.

Pseudocode:

RES = 0
FOR(i -> A to B) {
    FOR(j -> C to D) {
        ADD (i ^ j) to RES;
    }
}
PRINT(RES)

You are given the integers ‘A’, ‘B’, ‘C’, and ‘D’, and ‘^’ represents the bitwise XOR operator. As the result can be large print the result modulo 1000000007.

Input Format :

The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains 4 space-separated integers, representing the integers ‘A’, ‘B’, ‘C’, and ‘D’.

Output Format :

For each test case, print the result of the code modulo 1000000007.

Print the output of each test case in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= A <= B <= 5*10^3
1 <= C <= D <= 5*10^3

Time Limit : 1 sec

Solve now

Approaches

01 Approach

The basic idea is to find the count of numbers of set bits and unset bits for every bit. A digit can contribute to the result if the bit is set. A bit can be set in 2 ways with the help of XOR. (1 ^ 0) = (0 ^ 1) = 1.

So we need to find the count of numbers from ‘A’ to ‘B’ which have their bit set and count of numbers from ‘C’ to ‘D’ which have their bit unset and vice versa to calculate the result.

Here is the algorithm :

Create a variable (say, ‘RES’) used to store the result and initialize it with 0.
Run a loop from 0 to 30 (say, iterator ’i’) to traverse each bit.
- Run a loop from ‘A’ to ‘B’ (say, iterator ‘j’) to traverse all the numbers.
  - Find count of numbers having their ‘ith’ bit set and unset store them in the variables (say, ‘S0’ and ‘U0’) respectively.
- Run a loop from ‘C’ to ‘D’ (say, iterator ‘j’) to traverse all the numbers.
  - Find count numbers having their ‘ith’ bit set and unset stored in the variables (say, ‘S1’ and ‘U1’) respectively.
- Update ‘RES’ by adding bit value of sum ‘S0’ * ‘U1’ and ‘U0’ * ‘S1’.
Finally, return ‘RES’.

Solve now

02 Approach

The idea is to find the number of set bits from numbers 0 to ‘A’ - 1 and numbers from 0 to ‘B’ using shifting properties and subtract the result to get numbers having set bit at a particular bit from ‘A’ to ‘B’. We do the same process for numbers between ‘C’ to ‘D’. To calculate the result, we follow approach 1.

Here is the algorithm :

Create a variable (say, ‘RES’) used to store the number of palindromes.
Create a variable (say, ‘NUM0’) that will store the count of numbers present between ‘A’ to ‘B’.
Create a variable (say, ‘NUM1’) that will store the count of numbers present between ‘C’ to ‘D’.
Run a loop from 0 to 30 (say, iterator ’i’) to traverse each bit.
- Create a variable (say, ‘S0’) that will store the count of numbers present between ‘A’ to ‘B’ and having their ‘ith’ bit set and call the helper function which finds the count of numbers having their ‘ith’ bit set from 0 to ‘N’.
- Similarly, store the count of numbers present between ‘C’ to ‘D’ and having their ‘ith’ bit in a variable. (say, ‘S1’)
- Update ‘RES’ by adding the bit value of sum ‘S0’ * (‘NUM1’ - ‘S1’). ( Set0 * Unset1)
- Update ‘RES’ by adding bit value of sum (‘NUM0’ - ‘S0’) * ‘S1’. ( Unset0 * Set1)
Finally, return ‘RES’.

HELPER(N, I)

Right shift ‘N’ by ‘I’ + 1 times and do left shift ‘I’ times and store it in a variable (say, ‘TEMP’).
Check if the ‘Ith’ bit is set in ‘N’.
- Update ‘TEMP’ by adding the count of numbers from the nearest power of 2 less than ‘N’.
Finally, return ‘TEMP’.

Solve now