XOR की समस्याएँ

XOR एक game जैसा है जहां दो matching चीज़ें एक-दूसरे को cancel कर देती हैं, इसलिए जब सब कुछ paired up हो सिवाय एक के, सिर्फ odd one out बचता है।

In this page:

XOR Property
Find Single Number
Missing Number
Swap Using XOR
XOR Practice

Syntax

markup

result = 0
for x in arr:
    result ^= x    # pairs cancel out
# result holds the single number

XOR Property

XOR में दो properties हैं जो इसे puzzles में विशेष रूप से उपयोगी बनाती हैं: कोई भी value खुद के साथ XORed zero है (a ^ a = 0), और कोई भी value zero के साथ XORed unchanged रहती है (a ^ 0 = a) — साथ में ये matching pairs को पूरी तरह cancel out होने देते हैं।

उदाहरण: XOR Property

#include <iostream>
using namespace std;
int main() {
	int a = 7;
	cout << "a^a=" << (a^a) << " a^0=" << (a^0) << " -- self-cancels to 0, identity with 0 unchanged";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int a = 7;
		System.out.println("a^a=" + (a^a) + " a^0=" + (a^0) + " -- self-cancels to 0, identity with 0 unchanged");
	}
}

a = 7
print(f"a^a={a^a} a^0={a^0} -- self-cancels to 0, identity with 0 unchanged")

#include <stdio.h>
int main() {
	int a = 7;
	printf("a^a=%d a^0=%d -- self-cancels to 0, identity with 0 unchanged", a^a, a^0);
	return 0;
}

Find Single Number

अगर किसी array में हर number बिल्कुल दो बार दिखता है सिवाय एक number के जो सिर्फ एक बार दिखता है, हर element को एक साथ XOR करना सभी duplicate pairs को cancel कर देता है, सिर्फ single unmatched number result के रूप में छोड़ते हुए।

उदाहरण: Find Single Number

#include <iostream>
using namespace std;
int main() {
	int arr[] = {4,1,2,1,2};
	int result = 0;
	for (int x : arr) result ^= x;
	cout << "Duplicate pairs cancel, single number left: " << result;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {4,1,2,1,2};
		int result = 0;
		for (int x : arr) result ^= x;
		System.out.println("Duplicate pairs cancel, single number left: " + result);
	}
}

arr = [4,1,2,1,2]
result = 0
for x in arr:
    result ^= x
print("Duplicate pairs cancel, single number left:", result)

#include <stdio.h>
int main() {
	int arr[] = {4,1,2,1,2};
	int result = 0;
	for (int i = 0; i < 5; i++) result ^= arr[i];
	printf("Duplicate pairs cancel, single number left: %d", result);
	return 0;
}

Missing Number

जब एक array को 0 से n तक हर number रखना चाहिए लेकिन बिल्कुल एक गायब है, array के सभी numbers को 0 से n तक सभी numbers के साथ XOR करना दोनों में मौजूद हर number को cancel कर देता है, गायब वाले को पीछे छोड़ते हुए।

उदाहरण: Missing Number

#include <iostream>
using namespace std;
int main() {
	int arr[] = {0,1,3,4}, n = 4;
	int result = n;
	for (int i = 0; i < n; i++) result ^= i ^ arr[i];
	cout << "Missing number: " << result;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {0,1,3,4};
		int n = 4;
		int result = n;
		for (int i = 0; i < n; i++) result ^= i ^ arr[i];
		System.out.println("Missing number: " + result);
	}
}

arr = [0,1,3,4]
n = 4
result = n
for i in range(n):
    result ^= i ^ arr[i]
print("Missing number:", result)

#include <stdio.h>
int main() {
	int arr[] = {0,1,3,4}, n = 4;
	int result = n;
	for (int i = 0; i < n; i++) result ^= i ^ arr[i];
	printf("Missing number: %d", result);
	return 0;
}

Swap Using XOR

दो integer variables को sequence में तीन XOR operations उपयोग करके एक temporary variable के बिना swap किया जा सकता है (a ^= b; b ^= a; a ^= b;), पूरी तरह XOR की self-cancelling और identity properties पर निर्भर करते हुए एक extra storage slot के बजाय।

उदाहरण: Swap Using XOR

#include <iostream>
using namespace std;
int main() {
	int a = 5, b = 9;
	a ^= b; b ^= a; a ^= b;
	cout << "Swapped without a temp variable: a=" << a << " b=" << b;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int a = 5, b = 9;
		a ^= b; b ^= a; a ^= b;
		System.out.println("Swapped without a temp variable: a=" + a + " b=" + b);
	}
}

a, b = 5, 9
a ^= b
b ^= a
a ^= b
print(f"Swapped without a temp variable: a={a} b={b}")

#include <stdio.h>
int main() {
	int a = 5, b = 9;
	a ^= b; b ^= a; a ^= b;
	printf("Swapped without a temp variable: a=%d b=%d", a, b);
	return 0;
}

XOR Practice

XOR-based tricks interview problems में popular हैं specifically क्योंकि वे ऐसे tasks solve करती हैं जिन्हें आमतौर पर extra memory चाहिए (जैसे duplicates track करने के लिए एक hash set) सिर्फ constant extra space उपयोग करके, इसके लिए धन्यवाद कि duplicate values कितनी cleanly cancel out होती हैं।

उदाहरण: XOR Practice

#include <iostream>
using namespace std;
int main() {
	cout << "XOR tricks solve dedup-style tasks with O(1) extra space instead of a hash set";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("XOR tricks solve dedup-style tasks with O(1) extra space instead of a hash set");
	}
}

print("XOR tricks solve dedup-style tasks with O(1) extra space instead of a hash set")

#include <stdio.h>
int main() {
	printf("XOR tricks solve dedup-style tasks with O(1) extra space instead of a hash set");
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Power of Two Next Lesson → Top Array and String Problems