Given a range [L, R], the task is to find the XOR of all the integers in the given range i.e. (L) ^ (L + 1) ^ (L + 2) ^ … ^ (R)
Examples:
Input: L = 1, R = 4
Output: 4
1 ^ 2 ^ 3 ^ 4 = 4
Input: L = 3, R = 9
Output: 2
A simple solution is to find XOR of all the numbers iteratively from L to R. This will take linear time.
A better solution is to first find the most significant bit in the integer R. Our answer cannot have it’s a most significant bit larger than that of ‘R’. For each bit ‘i’ between 0 and MSB inclusive, we will try to determine the parity of count of a number of integers between L and R inclusive such that there ‘ith‘ bit is set. If the count is odd, then the ‘ith‘ bit of our final answer will also be set.
Now the real question is, for ith bit, how do we determine the parity of the count?
For an idea, let’s look at the binary representation of the first 16 integers.
0: 0000
1: 0001
2: 0010
3: 0011
4: 0100
5: 0101
6: 0110
7: 0111
8: 1000
9: 1001
10: 1010
11: 1011
12: 1100
13: 1101
14: 1110
15: 1111
It’s easily noticeable that the state of ith bit changes after every 2i number. We will use this idea to predict the count of a number of integers with ith bit set in the range L to R inclusive.
We have two cases here:
- Case 1(i != 0): We try to determine whether the ith bit of L is set or not. If set, we try to find the parity of the count of numbers between L and L + 2i inclusive, such that their ith bit is set. If ith bit of L is set and L is odd, then this count will be odd else even.
Similarly for R, we try to determine the parity of the count of a number of elements between R – 2i and R, such that their ith bit is set. If ith bit of L is set and L is even, then this count will be odd else even.
We ignore all the other integers in between because they will have even number of integers with ith bit set. - Case 2(i = 0): Here, we have the following cases:
- If L and R, both are odd, the count of the number of integers with 0th bit set will be (R – L)/2 + 1
- In any other case, the count will be floor((R – L + 1)/2).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the// most significant bitint msb(int x){ int ret = 0; while ((x >> (ret + 1)) != 0) ret++; return ret;}// Function to return the required XORint xorRange(int l, int r){ // Finding the MSB int max_bit = msb(r); // Value of the current bit to be added int mul = 2; // To store the final answer int ans = 0; // Loop for case 1 for (int i = 1; i <= max_bit; i++) { // Edge case when both the integers // lie in the same segment of continuous // 1s if ((l / mul) * mul == (r / mul) * mul) { if (((l & (1 << i)) != 0) && (r - l + 1) % 2 == 1) ans += mul; mul *= 2; continue; } // To store whether parity of count is odd bool odd_c = 0; if (((l & (1 << i)) != 0) && l % 2 == 1) odd_c = (odd_c ^ 1); if (((r & (1 << i)) != 0) && r % 2 == 0) odd_c = (odd_c ^ 1); // Updating the answer if parity is odd if (odd_c) ans += mul; // Updating the number to be added mul *= 2; } // Case 2 int zero_bit_cnt = zero_bit_cnt = (r - l + 1) / 2; if (l % 2 == 1 && r % 2 == 1) zero_bit_cnt++; if (zero_bit_cnt % 2 == 1) ans++; return ans;}// Driver codeint main(){ int l = 1, r = 4; // Final answer cout << xorRange(l, r); return 0;} |
Java
// Java implementation of the approach class GFG{ // Function to return the // most significant bit static int msb(int x) { int ret = 0; while ((x >> (ret + 1)) != 0) ret++; return ret; } // Function to return the required XOR static int xorRange(int l, int r) { // Finding the MSB int max_bit = msb(r); // Value of the current bit to be added int mul = 2; // To store the final answer int ans = 0; // Loop for case 1 for (int i = 1; i <= max_bit; i++) { // Edge case when both the integers // lie in the same segment of continuous // 1s if ((l / mul) * mul == (r / mul) * mul) { if (((l & (1 << i)) != 0) && (r - l + 1) % 2 == 1) ans += mul; mul *= 2; continue; } // To store whether parity of count is odd int odd_c = 0; if (((l & (1 << i)) != 0) && l % 2 == 1) odd_c = (odd_c ^ 1); if (((r & (1 << i)) != 0) && r % 2 == 0) odd_c = (odd_c ^ 1); // Updating the answer if parity is odd if (odd_c!=0) ans += mul; // Updating the number to be added mul *= 2; } // Case 2 int zero_bit_cnt = zero_bit_cnt = (r - l + 1) / 2; if (l % 2 == 1 && r % 2 == 1) zero_bit_cnt++; if (zero_bit_cnt % 2 == 1) ans++; return ans; } // Driver code public static void main(String args[]){ int l = 1, r = 4; // Final answer System.out.print(xorRange(l, r)); }} // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach# Function to return the most significant bitdef msb(x) : ret = 0 while ((x >> (ret + 1)) != 0) : ret = ret + 1 return ret# Function to return the required XORdef xorRange(l, r) : # Finding the MSB max_bit = msb(r) # Value of the current bit to be added mul = 2 # To store the final answer ans = 0 # Loop for case 1 for i in range (1, max_bit + 1) : # Edge case when both the integers # lie in the same segment of continuous # 1s if ((l // mul) * mul == (r // mul) * mul) : if ((((l & (1 << i)) != 0) and (r - l + 1) % 2 == 1)) : ans = ans + mul mul = mul * 2 continue # To store whether parity of count is odd odd_c = 0 if (((l & (1 << i)) != 0) and l % 2 == 1) : odd_c = (odd_c ^ 1) if (((r & (1 << i)) != 0) and r % 2 == 0) : odd_c = (odd_c ^ 1) # Updating the answer if parity is odd if (odd_c) : ans = ans + mul # Updating the number to be added mul = mul * 2 # Case 2 zero_bit_cnt = (r - l + 1) // 2 if ((l % 2 == 1 ) and (r % 2 == 1)) : zero_bit_cnt = zero_bit_cnt + 1 if (zero_bit_cnt % 2 == 1): ans = ans + 1 return ans# Driver codel = 1r = 4# Final answerprint(xorRange(l, r))# This code is contributed by ihritik |
C#
// C# implementation of the approach using System; class GFG{ // Function to return the // most significant bit static int msb(int x) { int ret = 0; while ((x >> (ret + 1)) != 0) ret++; return ret; } // Function to return the required XOR static int xorRange(int l, int r) { // Finding the MSB int max_bit = msb(r); // Value of the current bit to be added int mul = 2; // To store the final answer int ans = 0; // Loop for case 1 for (int i = 1; i <= max_bit; i++) { // Edge case when both the integers // lie in the same segment of continuous // 1s if ((l / mul) * mul == (r / mul) * mul) { if (((l & (1 << i)) != 0) && (r - l + 1) % 2 == 1) ans += mul; mul *= 2; continue; } // To store whether parity of count is odd int odd_c = 0; if (((l & (1 << i)) != 0) && l % 2 == 1) odd_c = (odd_c ^ 1); if (((r & (1 << i)) != 0) && r % 2 == 0) odd_c = (odd_c ^ 1); // Updating the answer if parity is odd if (odd_c!=0) ans += mul; // Updating the number to be added mul *= 2; } // Case 2 int zero_bit_cnt = zero_bit_cnt = (r - l + 1) / 2; if (l % 2 == 1 && r % 2 == 1) zero_bit_cnt++; if (zero_bit_cnt % 2 == 1) ans++; return ans; } // Driver code public static void Main(String []args){ int l = 1, r = 4; // Final answer Console.Write(xorRange(l, r)); }} // This code contributed by Rajput-Ji |
PHP
<?php// PHP implementation of the approach// Function to return the// most significant bitfunction msb($x){ $ret = 0; while (($x >> ($ret + 1)) != 0) $ret++; return $ret;}// Function to return the required XORfunction xorRange($l, $r){ // Finding the MSB $max_bit = msb($r); // Value of the current bit to be added $mul = 2; // To store the final answer $ans = 0; // Loop for case 1 for ($i = 1; $i <= $max_bit; $i++) { // Edge case when both the integers // lie in the same segment of continuous // 1s if ((int)(($l / $mul) * $mul) == (int)(($r / $mul) * $mul)) { if ((($l & (1 << $i)) != 0) && ($r - $l + 1) % 2 == 1) $ans += $mul; $mul *= 2; continue; } // To store whether parity of count is odd $odd_c = 0; if ((($l & (1 << $i)) != 0) && $l % 2 == 1) $odd_c = ($odd_c ^ 1); if ((($r & (1 << $i)) != 0) && $r % 2 == 0) $odd_c = ($odd_c ^ 1); // Updating the answer if parity is odd if ($odd_c) $ans += $mul; // Updating the number to be added $mul *= 2; } // Case 2 $zero_bit_cnt = (int)(($r - $l + 1) / 2); if ($l % 2 == 1 && $r % 2 == 1) $zero_bit_cnt++; if ($zero_bit_cnt % 2 == 1) $ans++; return $ans;}// Driver code$l = 1;$r = 4;// Final answerecho xorRange($l, $r);// This code is contributed by mits?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the// most significant bitfunction msb(x){ let ret = 0; while ((x >> (ret + 1)) != 0) ret++; return ret;}// Function to return the required XORfunction xorRange(l, r){ // Finding the MSB let max_bit = msb(r); // Value of the current bit to be added let mul = 2; // To store the final answer let ans = 0; // Loop for case 1 for (let i = 1; i <= max_bit; i++) { // Edge case when both the integers // lie in the same segment of continuous // 1s if ((parseInt(l / mul) * mul) == (parseInt(r / mul) * mul)) { if (((l & (1 << i)) != 0) && (r - l + 1) % 2 == 1) ans += mul; mul *= 2; continue; } // To store whether parity of count is odd let odd_c = 0; if (((l & (1 << i)) != 0) && l % 2 == 1) odd_c = (odd_c ^ 1); if (((r & (1 << i)) != 0) && r % 2 == 0) odd_c = (odd_c ^ 1); // Updating the answer if parity is odd if (odd_c) ans += mul; // Updating the number to be added mul *= 2; } // Case 2 let zero_bit_cnt = parseInt((r - l + 1) / 2); if (l % 2 == 1 && r % 2 == 1) zero_bit_cnt++; if (zero_bit_cnt % 2 == 1) ans++; return ans;}// Driver code let l = 1, r = 4; // Final answer document.write(xorRange(l, r));</script> |
Output:
4
Time Complexity: O(log2(R))
Auxiliary Space: O(1), since no extra space has been taken.
Efficient Approach: Let F(N) be a function that computes XOR of all the natural numbers less than or equal to N. Thus, for range (L-R), the answer will be F(R) ^ F(L-1).
Finding the value of this function for any given number is possible in O(1) as discussed in this article.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the required XORlong computeXOR(const int n){ // Modulus operator are expensive // on most of the computers. // n & 3 will be equivalent to n % 4 // n % 4 switch (n & 3) { // If n is a multiple of 4 case 0: return n; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return n + 1; // If n % 4 gives remainder 3 case 3: return 0; }}// Driver codeint main(){ int l = 1, r = 4; cout << (computeXOR(r) ^ computeXOR(l - 1)); return 0;} |
Java
// Java implementation of the approach class GFG { // Function to return the required XOR static long computeXOR(int n) { // Modulus operator are expensive // on most of the computers. // n & 3 will be equivalent to n % 4 // n % 4 int x = n & 3; switch (x) { // If n is a multiple of 4 case 0: return n; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return n + 1; // If n % 4 gives remainder 3 case 3: return 0; } return 0; } // Driver code public static void main(String args[]) { int l = 1, r = 4; System.out.println(computeXOR(r) ^ computeXOR(l - 1)); } } // This code is contributed by Ryuga |
Python3
# Python3 implementation of the approach# Function to return the required XORdef computeXOR(n) : # Modulus operator are expensive # on most of the computers. # n & 3 will be equivalent to n % 4 # n % 4 switch = { # If n is a multiple of 4 0 : n, # If n % 4 gives remainder 1 1 : 1, # If n % 4 gives remainder 2 2: n + 1, # If n % 4 gives remainder 3 3 : 0, } return switch.get( n & 3, "")# Driver codel = 1r = 4print(computeXOR(r) ^ computeXOR(l - 1))# This code is contributed by ihritik |
C#
// C# implementation of the approachusing System;class GFG{ // Function to return the required XORstatic long computeXOR(int n){ // Modulus operator are expensive // on most of the computers. // n & 3 will be equivalent to n % 4 // n % 4 int x=n&3; switch (x) { // If n is a multiple of 4 case 0: return n; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return n + 1; // If n % 4 gives remainder 3 case 3: return 0; } return 0;}// Driver codestatic void Main(){ int l = 1, r = 4; Console.WriteLine(computeXOR(r) ^ computeXOR(l - 1));}}// This code is contributed by mits |
PHP
<?php// PHP implementation of the approach // Function to return the required XOR function computeXOR($n) { // Modulus operator are expensive // on most of the computers. // n & 3 will be equivalent to n % 4 // n % 4 $x = $n & 3; switch ($x) { // If n is a multiple of 4 case 0: return $n; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return $n + 1; // If n % 4 gives remainder 3 case 3: return 0; } return 0; } // Driver code $l = 1; $r = 4; echo(computeXOR($r) ^ computeXOR($l - 1)); // This code is contributed by Code_Mech?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the required XORfunction computeXOR(n){ // Modulus operator are expensive // on most of the computers. // n & 3 will be equivalent to n % 4 // n % 4 switch (n & 3) { // If n is a multiple of 4 case 0: return n; // If n % 4 gives remainder 1 case 1: return 1; // If n % 4 gives remainder 2 case 2: return n + 1; // If n % 4 gives remainder 3 case 3: return 0; }}// Driver code let l = 1, r = 4; document.write(computeXOR(r) ^ computeXOR(l - 1));// This code is contributed by subhammahato348.</script> |
Output:
4
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
