Neighboring Bitwise XOR
Problem Statement
Given do positive integers num1 aur num2, aapko ek positive integer x find karna hai aisa jo:
xke set bits (binary representation mein ‘1’s ki count)num2ke set bits ke equal hox XOR num1ka value minimal ho (XOR ko bitwise XOR operation kaha jaata hai)
Aapko x return karna hai. Test cases aise honge ki x uniquely determined hoga. (Yani, ek hi sahi answer hoga).
Note: Ek integer ke set bits ka matlab hai uske binary representation mein ‘1’s ki count.
Examples:
Example 1:
Input: num1 = 3, num2 = 5 Output: 3 Explanation: num1 aur num2 ke binary representations 0011 aur 0101 hain. Sum of 1s in binary: num1 (3) has 2 set bits -> 0011 num2 (5) has 2 set bits -> 0101 Ek integer 3 hai jiska set bits ka count num2 ke equal hai, aur 3 XOR 3 = 0 minimal hota hai, because XOR operation for same numbers is zero.
Example 2:
Input: num1 = 1, num2 = 12 Output: 3 Explanation: num1 aur num2 ke binary representations 0001 aur 1100 hain. Sum of 1s in binary: num1 (1) has 1 set bit -> 0001 num2 (12) has 2 set bits -> 1100 Ek integer 3 hai jiska set bits ka count num2 ke equal hai, aur 3 XOR 1 = 2 minimal hota hai.
Constraints:
1 <= num1, num2 <= 10^9
Explanation:
Iss problem ko solve karne ke liye do steps hain:
Jitne set bits (binary ‘1’s)
num2mein hain, utne set bits wala integerxidentify karo.x XOR num1ka value minimal hona chahiye.
Pehle num2 ke set bits count karenge, phir possible x generate karenge, jise num1 ke saath XOR karenge aur minimum value identify karenge.
Neighboring Bitwise XOR
Agar cumulative XOR of derived array ka sum 0 hota hai, to ek valid binary array exist kar sakta hai. Agar nahi, to valid binary array exist nahi karega. Simplified form mein, iska matlab hai agar derived array ka XOR sum 0 hota hai, to kuch aisa original binary array banana possible hai jo derived array ko match karta hai.Is example se samajhte hain: Suppose derived = [1, 1, 0]Cumulative XOR calculation karo: 1 ⊕ 1 ⊕ 0 which results in 0.Yeh cumulative XOR 0 hone ke wajah se, ek valid original binary array exist karta hai jo derived array ko match karega.Lekin, agar derived array ka cumulative XOR 0 nahi hota: eg: derived = [1, 0]Cumulative XOR calculation karo: 1 ⊕ 0 which is 1.Yeh cumulative XOR 0 nahi hone ke wajah se, ek valid original array nahi banega jo derived array ko match kar sake.
Initialize a Variable:Ek variable xr ko initialize karna hai, jo cumulative XOR result ko store karega.Traverse Through Derived Array:Derived array ke har element ko traverse karenge, aur uss element ke saath XOR operation karke xr ko update karenge.Check Final Value:Traversal ke end pe, agar xr ka value 0 hai, to true return karenge, matlab ek valid binary array exist kar sakta hai.Agar xr ka value 0 nahi hota, to false return karenge, matlab koi valid binary array exist nahi kar sakta.
Time Complexity: O(n)
Hum derived array ke har element pe sirf ek baar iterate karte hain. Isliye time complexity linear hoti hai, yaani O(n). Iska matlab yeh hai ki agar array ke n elements hain, to maximum n operations hoge.
Space Complexity: O(1)
Hum sirf ek variable xr use karte hain cumulative XOR result compute karne ke liye. Isliye space constant hoti hai, yaani O(1). Iska matlab hai ki chahe array ka size kitna bhi ho, humein sirf ek hi variable ki zaroorat hai, jo fixed amount of memory occupy karega.
Solution
class Solution {
// Function to check kya valid original array exist karta hai
doesValidArrayExist(derived) {
// `xr` variable ko initialize karte hain cumulative XOR result store karne ke liye
let xr = 0;
// Derived array ke har element pe iterate karte hain
for (let val of derived) {
// `xr` ko update karte hain current element ke saath XOR operation se
xr ^= val;
}
// Check karte hain agar `xr` ka value 0 hai, to valid original array exist karega
return xr === 0;
}
}
Function Declaration:
Ek function hai
doesValidArrayExist, jo check karta hai agar valid original array exist karta hai jo derived array ko form karta ho.
Initialize Variable:
Sabse pehle, ek variable
xrko initialize karte hain jo cumulative XOR result ko store karega.
Iterate Through Derived Array:
Derived array ke har element pe iterate karte hain.
Har iteration mein, derived array ke current element ke saath XOR operation karke
xrko update karte hain.
Check Final Value:
Jab saare elements pe iterate kar lete hain, to final value check karte hain.
Agar
xrka value 0 hai, to functiontruereturn karta hai, which means valid original array exist karta hai.Agar
xrka value 0 nahi hota, to functionfalse
Solution
class Solution {
public:
// Function to check kya ek valid original array exist karta hai jo derived array ko form kar sakta ho
bool doesValidArrayExist(vector<int>& derived) {
// `xr` variable ko initialize karte hain cumulative XOR result store karne ke liye
int xr = 0;
// Derived array ke har element pe iterate karte hain
for (auto val : derived) {
// `xr` ko update karte hain current element ke saath XOR operation se
xr ^= val;
}
// Agar `xr` ki final value 0 hai, to valid original array exist karta hai
return xr == 0;
}
};
Function Declaration:
Ek function
doesValidArrayExistdeclare kiya gaya hai, jo check karta hai agar ek valid original array exist karta hai jo derived array ko form kar sakta ho.
Initialize Variable:
Function ke shuruaat mein ek variable
xrinitialize kiya gaya hai, jo cumulative XOR result store karega.
Iterate Through Derived Array:
Derived array ke har element par iterate kiya gaya hai.
Har iteration mein derived array ke current element ko
xrvariable ke saath XOR operation karke update kiya gaya hai.
Check Final Value:
Jab saare elements par iterate kar lete hain, to final value check ki jaati hai.
Agar
xrka value 0 hai, to functiontruereturn karta hai, jo indicate karta hai ki ek valid original array exist karta hai jo derived array ko form kar sakta hai.Agar
xrka value 0 nahi hota, to functionfalsereturn karta hai, jo indicate karta hai ki koi valid original array exist nahi karta.
