XOR очень больших двоичных чисел в диапазоне [L, R]

Даны две двоичные строки L и R , задача состоит в том, чтобы найти xor из L в R. Длина двоичной строки < = 10e6 .

Примеры:

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 
 

Наивный подход: самый простой подход к решению проблемы — найти все двоичные строки в диапазоне [L, R], а затем выполнить операцию XOR для всех двоичных строк.

Временная сложность: (R – L +1) *(N), где N — длина двоичной строки R.
Вспомогательное пространство: O(1)

Эффективный подход . Вышеупомянутый подход можно дополнительно оптимизировать, заметив, что:

• (L ^ (L+1) ^……^(R – 1) ^ R) можно записать как (1^2^3 ^…. ^(R-1)^R) ^ (1^2^3 … .. ^(L-2) ^ (L-1)) где '^' обозначает побитовое исключающее ИЛИ элементов. Таким образом, задача сводится к поиску xor от 1 до n.
• Чтобы вычислить xor от 1 до n, найдите остаток n , модулируя его с помощью 4 , и сохраните его в переменной, скажем, rem , и есть четыре возможных значения rem —
  • Если rem =0 , то xor = n .
  • Если rem = 1 , то xor = 1 .
  • Если rem = 2 , то xor = n+1 .
  • Если rem = 3 , то xor = 0 .

Соблюдая вышеуказанные пункты, выполните следующие шаги, чтобы решить проблему:

• Создайте функцию sub , которая вычитает 1 из двоичной строки S размера N, выполнив шаги, указанные ниже:
  • Выполните итерацию в диапазоне [N-1, 0], используя переменную i , и выполните следующие шаги:
    • Если S[i] = '0' , измените значение S[i] на 1.
    • Если S[i] = '1' , измените значение S[i] на 0 и завершите цикл.
  • Возвращает строку S в качестве ответа.
• Создайте функцию ad , которая добавляет 1 к двоичной строке S размера N, выполнив шаги, указанные ниже:
  • Инициализируйте переменную, скажем, переносите как 0 .
  • Выполните итерацию в диапазоне [N-1, 0], используя переменную i , и выполните следующие шаги:
    • Если S[i] = '1' , измените значение S[i] на 0 и измените значение переноса на 1 .
    • Если S[i] = '0' , измените значение S[i] на 1 и измените значение переноса на 0 и завершите цикл.
  • Если перенос =1 , то измените значение S как '1' + S и верните строку S.
• Создайте функцию Xor_Finder , которая возвращает значение XOR от 1 до S , выполнив шаги, указанные ниже:
  • Инициализируйте переменную, скажем, val , и обновите значение как S[n] + S[n-1]*2 , где n — длина строки S.
  • Теперь, если val = 0 , верните строку S в качестве ответа.
  • Если val = 1 , то верните '1' в качестве ответа.
  • Если val = 2 , то вернуть ad(S) в качестве ответа.
  • Если val = 3 , то вернуть 0 в качестве ответа.
• Создайте функцию final_xor , которая вычисляет xor двух двоичных строк L и R, выполнив шаги, указанные ниже:
  • Добавьте символ '0' к строке L , пока L.size() != R.size() .
  • Инициализируйте строку, скажем, an , которая будет хранить значение xor двоичных строк L и R.
  • Выполните итерацию в диапазоне [0, R.size()-1] , используя переменную i , и выполните следующие шаги:
    • Если L[i] = R[i] , добавьте символ '0' в конец строки ans.
    • Если L[i] != R[i] , добавьте символ '1' в конце строки ответа.
  • Возвращает строку как операцию xor двух строк.
• Создайте функцию xorr для вычисления xor от L до R , выполнив следующие шаги:
  • Измените значение L как sub(L) .
  • Измените значение L и R , вызвав функции xor_finder(L) и xor_finder(R) для вычисления xor от 1 до L и от 1 до R соответственно.
  • Инициализируйте переменную, скажем, ans , и обновите значение ans , обновив значение как final_xor(L, R) .
  • Вернуть строку в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N), где N — длина строки.
Вспомогательное пространство: O(N)