# XOR of very large Binary Numbers in range [L, R]

Given two binary strings **L** and **R**, the task is to find the xor from L to R. Length of the binary string is **< = 10e6**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:L = 10, R = 100Output:101Explanation:L = 2 and R = 4 in decimal system.Therefore, the xor will be 2^3^4 = 5(101).

Input:L = 10, R = 10000Output: 10001

**Naive Approach:** The simplest approach to solve the problem is to find all the binary strings in the range** [L, R]** and then perform the XOR operation on all the binary strings.

**Time Complexity:** (R – L +1) *(N) where N is the length of binary string R.**Auxiliary Space: **O(1)

**Efficient Approach: **The above approach can be optimized further by observing that –

**(L ^ (L+1) ^……^(R – 1) ^ R)**can be written as**(1^2^3 ^…. ^(R-1)^R) ^ (1^2^3 ….. ^(L-2) ^ (L-1))**where ‘^’ denotes the bitwise xor of the elements. So the problem is reduced to find the xor from 1 to n.- To calculate xor from 1 to n, find the remainder of
**n**by moduling it with**4**and store it in a variable, say**rem**and there are four possible values of**rem**–- If
**rem =0**then**xor = n**. - If
**rem = 1**then**xor = 1**. - If
**rem = 2**then**xor = n+1**. - If
**rem = 3**then**xor = 0**.

- If

After observing the above points, follow the steps below to solve the problem:

- Create a function
**sub**that subtracts 1 from a binary string S of size N by performing the steps mentioned below:- Iterate in the range
**[N-1, 0]**using the variable**i**and perform the following steps:- If
**S[i] = ‘0’**, then modify the value of**S[i]**as**1.** - If
**S[i] = ‘1’**, then modify the value of**S[i]**as**0**and terminate the loop.

- If
- Return string
**S**as the answer.

- Iterate in the range
- Create a function
**ad**that adds 1 to a binary string S of size N by performing the steps mentioned below:- Initialize a variable, say
**carry**as**0**. - Iterate in the range
**[N-1, 0]**using the variable**i**and perform the following steps:- If
**S****[i****] = ‘1’**, then modify the value of**S[i]**as**0**and modify the value of**carry**as**1**. - If
**S[i] = ‘0’**, then modify the value of**S[i]**as**1**and modify the value of**carry**as**0**and terminate the loop.

- If
- If
**carry =1**, then modify the value of**S**as**‘1’ + S**and return the string**S**.

- Initialize a variable, say
- Create a function
**Xor_Finder**which return the value of XOR from**1**to**S**by performing the steps mentioned below:- Initialize a variable, say
**val**and update the value as**S[n] + S[n-1]*2**where n is the length of the string S. - Now if
**val = 0**, then return string**S**as the answer. - If
**val = 1**, then return ‘1’ as the answer. - If
**val = 2**, then return**ad(S)**as the answer. - If
**val = 3**, then return 0 as the answer.

- Initialize a variable, say
- Create a function
**final_xor**which calculate xor of two binary strings L and R by performing the steps mentioned below:- Append character ‘0’ to the string
**L**while**L.size() != R.size()**. - Initialize a string, say
**ans**that will store the value of xor of binary strings**L**and**R**. - Iterate in the range
**[0, R.size()-1]**using the variable**i**and perform the following steps:- If
**L[i] = R[i]**, then append the character ‘0’ at the end of string ans. - If
**L[i] != R[i]**, then append the character ‘1’ at the end of string ans.

- If
- Return string
**ans**as the xor of the two strings.

- Append character ‘0’ to the string
- Create a function
**xorr**to calculate xor from**L**to**R**by performing the following steps:- Modify the value of
**L**as**sub(L)**. - Modify the value of
**L**and**R**by calling the function**xor_finder(L)**and**xor_finder(R)**to calculate xor from**1**to**L**and from**1**to**R**respectively. - Initialize a variable, say
**ans**and update the value of**ans**by updating the value as**final_xor(L, R)**. - Return string
**ans**as the answer.

- Modify the value of

Below is the implementation of the above approach:

## C++

`// C++ program for the above approach` `#include <iostream>` `using` `namespace` `std;` ` ` `// Function to subtract one` `// from the binary string` `string sub(string s)` `{` ` ` `int` `n = s.size();` ` ` `for` `(` `int` `i = n - 1; i >= 0; i--) {` ` ` `// If the current character` ` ` `// is 0 change it to 1` ` ` `if` `(s[i] == ` `'0'` `) {` ` ` `s[i] = ` `'1'` `;` ` ` `}` ` ` `else` `{` ` ` `// If the character is 1` ` ` `// Change is to 0 and` ` ` `// terminate the loop` ` ` `s[i] = ` `'0'` `;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// Return the answer` ` ` `return` `s;` `}` ` ` `// Function to add 1 in the` `// binary string` `string ad(string s)` `{` ` ` `int` `n = s.size();` ` ` ` ` `int` `carry = 0;` ` ` `for` `(` `int` `i = n - 1; i >= 0; i--) {` ` ` `// If s[i]=='1' it` ` ` `// will change s[i] to 0` ` ` `// and carry = 1` ` ` `if` `(s[i] == ` `'1'` `) {` ` ` `carry = 1;` ` ` `s[i] = ` `'0'` `;` ` ` `}` ` ` `else` `{` ` ` `// If s[i]=='0' it` ` ` `// will change s[i] to 1` ` ` `// and carry = 0 and` ` ` `// end the loop` ` ` `carry = 0;` ` ` `s[i] = ` `'1'` `;` ` ` `break` `;` ` ` `}` ` ` `}` ` ` `// If still carry left` ` ` `// append character 1 to the` ` ` `// beginning of the string` ` ` `if` `(carry) {` ` ` `s = ` `'1'` `+ s;` ` ` `}` ` ` `return` `s;` `}` ` ` `// Function to find xor from 1 to n` `string xor_finder(string s)` `{` ` ` `int` `n = s.size() - 1;` ` ` ` ` `// Variable val stores the` ` ` `// remainder when binary string` ` ` `// is divided by 4` ` ` `int` `val = s[n] - ` `'0'` `;` ` ` `val = val + (s[n - 1] - ` `'0'` `) * 2;` ` ` ` ` `// If val == 0 the xor from` ` ` `// 1 to n will be n itself` ` ` `if` `(val == 0) {` ` ` `return` `s;` ` ` `}` ` ` `else` `if` `(val == 1) {` ` ` `// If val == the xor from` ` ` `// 1 to n will be 1 itself` ` ` `s = ` `'1'` `;` ` ` `return` `s;` ` ` `}` ` ` `else` `if` `(val == 2) {` ` ` `// If val == 2 the xor from` ` ` `// 1 to n will be n+1 itself` ` ` `return` `(ad(s));` ` ` `}` ` ` `else` `if` `(val == 3) {` ` ` `// If val == 3 the xor from` ` ` `// 1 to n will be 0 itself` ` ` `s = ` `'0'` `;` ` ` `return` `s;` ` ` `}` `}` `// Function to find the xor of two` `// binary string` `string final_xor(string L, string R)` `{` ` ` `// Using loop to equalise the size` ` ` `// of string L and R` ` ` `while` `(L.size() != R.size()) {` ` ` `L = ` `'0'` `+ L;` ` ` `}` ` ` `string ans = ` `""` `;` ` ` `for` `(` `int` `i = 0; i < L.size(); i++) {` ` ` `// If ith bit of L is 0 and` ` ` `// ith bit of R is 0` ` ` `// then xor will be 0` ` ` `if` `(L[i] == ` `'0'` `&& R[i] == ` `'0'` `) {` ` ` `ans += ` `'0'` `;` ` ` `}` ` ` `else` `if` `(L[i] == ` `'0'` `&& R[i] == ` `'1'` ` ` `|| L[i] == ` `'1'` `&& R[i] == ` `'0'` `) {` ` ` `// If ith bit of L is 0 and` ` ` `// ith bit of R is 1 or` ` ` `// vice versa then xor will be 1` ` ` `ans += ` `'1'` `;` ` ` `}` ` ` `else` `{` ` ` `// If ith bit of L is 1 and` ` ` `// ith bit of R is 1` ` ` `// then xor will be 0` ` ` `ans += ` `'0'` `;` ` ` `}` ` ` `}` ` ` `return` `ans;` `}` ` ` `// Function to find xor from L to R` `string xorr(string L, string R)` `{` ` ` `// changing L to L - 1` ` ` `L = sub(L);` ` ` ` ` `// Finding xor from 1 to L - 1` ` ` `L = xor_finder(L);` ` ` ` ` `// Finding xor from 1 to R` ` ` `R = xor_finder(R);` ` ` ` ` `// Xor of 1, 2, ..., L-1 and 1, 2, ...., R` ` ` `string ans = final_xor(L, R);` ` ` ` ` `return` `ans;` `}` ` ` `// Driver Code` `int` `main()` `{` ` ` `// Given Input` ` ` `string L = ` `"10"` `, R = ` `"10000"` `;` ` ` ` ` `// Function Call` ` ` `cout << xorr(L, R) << endl;` ` ` `return` `0;` `}` |

**Output:**

10001

**Time Complexity: **O(N) where N is the length of the string**Auxiliary Space: **O(N)