Data Modelling & AI Data Structure & Algorithm

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

23 June 2025

3

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:

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

Input: L = 10, R = 10000
Output: 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.

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.
- Return string S as the answer.
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 carry =1, then modify the value of S as ‘1’ + S and return the string S.
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.
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.
- Return string ans as the xor of the two strings.
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.

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;
}

Java

// Java program for above approach 
class GFG{
     
// Function to subtract one
// from the binary string
public static String sub(String s)
{
    StringBuilder new_s = new StringBuilder(s);
    int n = s.length();
    for(int i = n - 1; i >= 0; i--)
    {
         
        // If the current character
        // is 0 change it to 1
        if (s.charAt(i) == '0')
        {
            new_s.setCharAt(i, '1');
        }
        else
        {
             
            // If the character is 1
            // Change is to 0 and
            // terminate the loop
            new_s.setCharAt(i, '0');
            break;
        }
    }
     
    // Return the answer
    return new_s.toString();
}
 
// Function to add 1 in the
// binary string
public static String ad(String s)
{
    int n = s.length();
    StringBuilder new_s = new StringBuilder(s);
    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.charAt(i) == '1') 
        {
            carry = 1;
            new_s.setCharAt(i, '0');
        }
        else
        {
             
            // If s[i]=='0' it
            // will change s[i] to 1
            // and carry = 0 and
            // end the loop
            carry = 0;
            new_s.setCharAt(i, '1');
            break;
        }
    }
     
    // If still carry left
    // append character 1 to the
    // beginning of the string
    if (carry != 0) 
    {
        s = '1' + new_s.toString();
    }
    return s;
}
 
// Function to find xor from 1 to n
public static String xor_finder(String s)
{
    int n = s.length() - 1;
 
    // Variable val stores the
    // remainder when binary string
    // is divided by 4
    int val = s.charAt(n) - '0';
    val = val + (s.charAt(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 == 1 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 the xor from
        // 1 to n will be 0 itself
        s = "0";
        return s;
    }
}
 
// Function to find the xor of two
// binary string
public static String final_xor(String L, String R)
{
     
    // Using loop to equalise the size
    // of string L and R
    while (L.length() != R.length()) 
    {
        L = '0' + L;
    }
    String ans = "";
    for(int i = 0; i < L.length(); i++) 
    {
         
        // If ith bit of L is 0 and
        // ith bit of R is 0
        // then xor will be 0
        if (L.charAt(i) == '0' && R.charAt(i) == '0')
        {
            ans += '0';
        }
        else if (L.charAt(i) == '0' && R.charAt(i) == '1' || 
                 L.charAt(i) == '1' && R.charAt(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
public static 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
public static void main(String[] args)
{
     
    // Given Input
    String L = "10", R = "10000";
 
    // Function Call
    System.out.println(xorr(L, R));
}
}
 
// This code is contributed by garry133

Python3

# Python program for the above approach
 
# Function to subtract one
# from the binary string
def sub(s):
   
    # Changing string into list to change
    # the characters in O(1)
    s = list(s)
    n = len(s)
    for i in range(n-1, -1, -1):
       
        # 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
    # converting list to string
    s = "".join(s)
    return s
 
# Function to add 1 in the
# binary string
 
 
def ad(s):
    n = len(s)
    carry = 0
    for i in range(n-1, -1, -1):
        # 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
 
 
def xor_finder(s):
    n = len(s) - 1
 
    # Variable val stores the
    # remainder when binary string
    # is divided by 4
    val = ord(s[n]) - 48
    val = val + (ord(s[n - 1]) - 48) * 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
 
 
def final_xor(L, R):
    # Using loop to equalise the size
    # of string L and R
    while (len(L) != len(R)):
        L = '0' + L
    ans = ""
    for i in range(len(L)):
        # If ith bit of L is 0 and
        # ith bit of R is 0
        # then xor will be 0
        if (L[i] == '0' and R[i] == '0'):
            ans += '0'
        else if (L[i] == '0' and R[i] == '1'
              or L[i] == '1' and 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
 
 
def xorr(L, 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
    ans = final_xor(L, R)
 
    return ans
 
# Driver Code
 
# Given Input
L = "10"
R = "10000"
 
# Function Call
print(xorr(L, R))
 
# This code is contributed by rj13to.

C#

// C# program for above approach
using System;
using System.Collections.Generic;
 
class GFG 
{
 
  // Function to subtract one
  // from the binary string
  public static string Sub(string s)
  {
 
    int n = s.Length;
    char[] new_s = new char[n];
    for (int i = n - 1; i >= 0; i--)
    {
 
      // If the current character
      // is 0 change it to 1
      if (s[i] == '0') {
        new_s[i] = '1';
      }
      else
      {
 
        // If the character is 1
        // Change is to 0 and
        // terminate the loop
        new_s[i] = '0';
        break;
      }
    }
    // Return the answer
    return new string(new_s);
  }
 
  // Function to add 1 in the
  // binary string
  public static string Ad(string s)
  {
    int n = s.Length;
    char[] new_s = new char[n];
    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;
        new_s[i] = '0';
      }
      else {
        // If s[i]=='0' it
        // will change s[i] to 1
        // and carry = 0 and
        // end the loop
        carry = 0;
        new_s[i] = '1';
        break;
      }
    }
    // If still carry left
    // append character 1 to the
    // beginning of the string
    if (carry != 0) {
      s = '1' + (new string(new_s));
    }
    return s;
  }
 
  // Function to find xor from 1 to n
  public static string XorFinder(string s)
  {
    int n = s.Length - 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 == 1 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 the xor from
      // 1 to n will be 0 itself
      s = "0";
      return s;
    }
  }
 
  // Function to find the xor of two
  // binary string
  private static string final_xor(string L, string R)
  {
    // Using loop to equalise the size
    // of string L and R
    while (L.Length != R.Length) {
      L = '0' + L;
    }
    string ans = "";
    for (int i = 0; i < L.Length; 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;
  }
 
  private static string xorr(string L, string R)
  {
    // Changing L to L - 1
    L = Sub(L);
 
    // Finding xor from 1 to L - 1
    L = XorFinder(L);
 
    // Finding xor from 1 to R
    R = XorFinder(R);
 
    // Xor of 1, 2, ..., L-1 and 1, 2, ...., R
    string ans = final_xor(L, R);
 
    return ans;
  }
 
  public static void Main(string[] args)
  {
    // Given Input
    string L = "10", R = "10000";
 
    // Function Call
    Console.WriteLine(xorr(L, R));
  }
}
 
// This code is contributed by phasing17

Javascript

// Function to subtract one
// from the binary string
function sub(s)
{
    // Changing string into array to change
    // the characters in O(1)
    s = s.split('');
    let n = s.length;
    for (let 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 it to 0 and
            // terminate the loop
            s[i] = '0';
            break;
        }
    }
    // Return the answer
    // converting array to string
    s = s.join('');
    return s;
}
 
// Function to add 1 in the
// binary string
function ad(s)
{
    let n = s.length;
    let carry = 0;
    for (let 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
function xor_finder(s)
{
    let n = s.length - 1;
 
    // Variable val stores the
    // remainder when binary string
    // is divided by 4
    let val = s.charCodeAt(n) - 48;
    val = val + (s.charCodeAt(n - 1) - 48) * 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
function final_xor(L, R)
{
    // Using loop to equalize the size
    // of string L and R
    while (L.length != R.length) {
        L = '0' + L;
    }
    ans = "";
    for (i = 0; i < L.length; i++) {
        if (L[i] == '0' && R[i] == '0') {
            ans += '0';
        }
        else if (L[i] == '0' && R[i] == '1' || L[i] == '1' && R[i] == '0') {
            ans += '1';
        }
        else {
            ans += '0';
        }
    }
    return ans;
}
 
function xorr(L, 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
    ans = final_xor(L, R);
 
    return ans;
}
 
// Driver Code
 
// Given Input
L = "10";
R = "10000";
 
// Function Call
console.log(xorr(L, R));
 
// This code is contributed by phasing17.

Output:

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

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!

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

C++

Java

Python3

C#

Javascript

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

Google is working on vertical tabs for Chrome

Gemini can now tell you whether that image is real or AI-generated

Google Phone could soon let urgent calls cut through DND

Google AI Mode brings an unwelcome surprise as ads start populating searches

EDITOR PICKS

Google is working on vertical tabs for Chrome

Gemini can now tell you whether that image is real or AI-generated

Google Phone could soon let urgent calls cut through DND

POPULAR POSTS

Google is working on vertical tabs for Chrome

Gemini can now tell you whether that image is real or AI-generated

Google Phone could soon let urgent calls cut through DND

POPULAR CATEGORY

ABOUT US

FOLLOW US