Optimize The Code

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
13 upvotes
Asked in companies
UberCarXNagarro Software

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 3 7 8
1 1 1 1
Sample Output 1 :
30
0
Explanation For Sample Input 1 :
For the first test case :

The operations performed will be : 2^7 + 2^8 + 3^7 + 3^8 = 5 + 10 + 4 + 11 = 30

For the second test :

The operations performed will be : 1^1 + 1^1 = 0 + 0 = 0
Sample Input 2 :
2
3 5 4 5
1 2 3 4
Sample Output 2 :
15
14
Hint

Try checking the number of set bits and unset bits at every bit.

Approaches (2)
Bit Manipulation

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 :

 

  1. Create a variable (say, ‘RES’) used to store the result and initialize it with 0.
  2. 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’.
  3. Finally, return ‘RES’.
Time Complexity

O(max(B - A, D - C)), where ‘A’, ‘B’, ‘C’, and ‘D’ are given integers.

 

We traverse all the bits possible and for each bit, we find the count of numbers that have their ‘ith’ bit set or unset from ‘A’ to ‘B’ and ‘C’ to ‘D’. Therefore, the overall time complexity will be O(31 * max(B - A, D - C)), i.e., O(max(B - A, D - C)).

Space Complexity

O(1)

 

We are not using any extra space. Therefore, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Optimize The Code
Full screen
Console