Coding - Find a bitwise XOR for a range of numbers in java

Question

Find a bitwise XOR for a range for.e.g (5,8) --> 5 bitXOR 6 | 7 bitXOR 8 3 bitXOR 15 12

Expected worst time Complexity - O(log(n))

Expected worst space Complexity - O(1)

I have written the below code, could you please help me to improve it?

static List<Integer> list;
 public static void main(String[] args) {
 int bitXORProduct = solution(5,8);
 System.out.println(bitXORProduct);
 }
 public static int solution(int M, int N) {
 if (isValidatedInput(M, N)) {
 int lastXOR = M;
 int currentXOR = 0;
 try {
 for (int i = M; i < N; i++) {
 currentXOR = computeXOR(lastXOR, i + 1);
 lastXOR = currentXOR;
 }
 } catch (Exception e) {
 System.out.println("Error Found : -" + e);
 }
 return lastXOR;
 }
 System.out.println("Input is not in the range or valid");
 return -1;
 }
 private static boolean isValidatedInput(int M, int N) {
 if (0 <= M && 0 <= N && M <= Math.pow(10, 9) && N <= Math.pow(10, 9) && M <= N) {
 return true;
 } else
 return false;
 }
 private static Integer computeXOR(Integer m, Integer n) {
 return m ^ n;
 }

• Mast: Cross-posted on Stack Overflow
• greybeard: I do not understand the example. How do I interpret the vertical bar (|)? How do 15 12 turn up? I might understand 5 ^ 6 ^ 7 ^ 8 = 3 ^ 15 = 12 - or the verbose bitXOR. How does the Expected worst time Complexity - O(log(n)) come up?

Answer 1

First of all the solution you have given is complexity O(n), not O(log(n)). It is possible to do it in O(log(n)) by calculating the result bit by bit. For example, suppose I have a range of four consecutive integers. Then I know that two of those numbers are odd and two of those numbers are even. Since only odd numbers have the first bit set I already know that XOR-ing the four numbers will leave the first bit at 0. For the second bit, I notice that for each set of four consecutive numbers there is always one number 2 mod 4 and one number 3 mod 4. Since all integers which have the second bit set ar either 2 or 3 mod 4, I know that XOR-ing the set of four integers will leave the second bit at 0. In this way I can determine for each bit if it should be set or not by looking at the properties of the numbers in the range. Usually this can be done in O(1) by only using the boundries of the range. Since there are log₂(n) rounded up bits in n, this solution will have complexity O(log(n)).

On to the code.

static List<Integer> list;

This list is not needed, it can be removed.

public static int solution(int M, int N)

The name of the method is solution but it doesn't describe what it is doing. Try to give it a name in accordance with it's function, something like computeXorForRange perhaps. Also, all other variables and methods in your code are camelCase so for consistency you should make M and N lower case. Or you can rename them to lowerBound and upperBoundInclusive if you like to tell the reader what they represent.

int lastXOR = M;
currentXOR = 0;
try {
 for (int i = M; i < N; i++) {
 currentXOR = computeXOR(lastXOR, i + 1);
 lastXOR = currentXOR;
 }
} catch (Exception e) {
 System.out.println("Error Found : -" + e);
}

In this part it is not needed to have to different variables, currentXOR and lastXOR. One should be enough. Having the two variables here makes it more complex than it should be. Also, why are you catching exceptions here? What exceptions do you expect to happen? Since the code used in the try does not throw any exception except for the possible standard java runtime exceptions like for example OutOfMemoryException, it is not needed to have a try catch.

System.out.println("Input is not in the range or valid");
return -1;

This part is at the end of the method. Instead you can negate the if statement at the beginning of the method and put this piece in the if. Then it becomes more clear what happens if the conditions are not met. There is also a return -1 which is more of a C style thing. In this case it is perfectly fine to use an Exception, the IllegalArgumentException will fit since the arguments passed are not valid (they are too small or too large).

private static boolean isValidatedInput(int M, int N) {
 if (0 <= M && 0 <= N && M <= Math.pow(10, 9) && N <= Math.pow(10, 9) && M <= N) {
 return true;
 } else
 return false;
}

The name of the method can be changed to isValidInput. The name isValidatedInput suggests that there will be a check if the input is already validated while it seems you are validating the input. There us also no reason to have the return true and return false, you can immediatly return the condition used in the if. Because if that condition is true the method will then return true and if the condition is false the method will then return false. Lastly, the upper bound of 10^9 seems arbitrary. If you want to prevent overflows and underflows you can use Integer.MAX_VALUE as upper bound.

private static Integer computeXOR(Integer m, Integer n) {
 return m ^ n;
}

In the rest of the code you use int yet here you use Integers. Using Integer is not necessary in this case since you don't have to deal with null values so using int would be consistent with the rest of the code. You can also ask if this method is really needed. IMO something like x ^ y is perfectly fine and clear and you don't need a separate method for that, but if it helps you, you can leave it in.

All in all with the above suggestions the code will become

public static void main(String[] args) {
 int bitXORProduct = solution(5,8);
 System.out.println(bitXORProduct);
}
public static int solution(int lowerBound, int upperBoundInclusive) {
 if (!isValidInput(lowerBound, upperBoundInclusive)) {
 throw new IllegalArgumentException("Input is not in the range or valid");
 }
 int currentXOR = lowerBound;
 for (int i = lowerBound; i < upperBoundInclusive; i++) {
 currentXOR = currentXOR ^ (i + 1); // this can also be written as currentXOR ^= i + 1;
 }
 return currentXOR;
}
private static boolean isValidInput(int M, int N) {
 return 0 <= M
 && 0 <= N
 && M <= Math.pow(10, 9)
 && N <= Math.pow(10, 9)
 && M <= N;
}
```