Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Intuition & First Thoughts
Wassup anh em coder! 🌟
Sau loạt bài về bit manipulation, hôm nay chúng ta tiếp tục “cà khịa” với binary array kết hợp XOR. Nhìn qua có vẻ phức tạp nhưng thực ra solution lại cực kỳ elegant! Cùng “hack” nó thôi! 💻
Chào anh em, các ae có thể xem Đề bài và Solution của mình trên LeetCode nhé:
- Đề bài: Xem tại đây
- Solution: Xem tại đây
2683. Neighboring Bitwise XOR
MediumA 0-indexed array derived with length n is derived by computing the bitwise XOR (⊕) of adjacent values in a binary array original of length n.
Specifically, for each index i in the range [0, n - 1]:
- If
i = n - 1, thenderived[i] = original[i] ⊕ original[0]. - Otherwise,
derived[i] = original[i] ⊕ original[i + 1].
Given an array derived, your task is to determine whether there exists a valid binary array original that could have formed derived.
Return true if such an array exists or false otherwise.
A binary array is an array containing only 0’s and 1’s.
Example 1:
Input: derived = [1,1,0] Output: true Explanation: A valid original array that gives derived is [0,1,0]. derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1 derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0
Example 2:
Input: derived = [1,1] Output: true Explanation: A valid original array that gives derived is [0,1]. derived[0] = original[0] ⊕ original[1] = 1 derived[1] = original[1] ⊕ original[0] = 1
Example 3:
Input: derived = [1,0] Output: false Explanation: There is no valid original array that gives derived.
Constraints:
n == derived.length1 <= n <= 10^5- The values in derived are either 0's or 1's
Solution 1: Construction Method - Xây Dựng Từng Bước
Intuition của Solution 1
Quan sát quan trọng:
- Nếu có original hợp lệ bắt đầu bằng 0, sẽ có original hợp lệ bắt đầu bằng 1
- Tại sao? Vì tính chất đối xứng của XOR!
Ví dụ minh họa:
derived = [1,1,0]
Nếu original[0] = 0:
0 ⊕ x = 1 -> x = 1 -> original[1] = 1
1 ⊕ y = 1 -> y = 0 -> original[2] = 0
0 ⊕ 0 = 0 ✓ (điều kiện cuối)
Nếu original[0] = 1:
1 ⊕ x = 1 -> x = 0 -> original[1] = 0
0 ⊕ y = 1 -> y = 1 -> original[2] = 1
1 ⊕ 1 = 0 ✓ (điều kiện cuối)Approach 1
- Giả sử
original[0] = 0(ta có thể chọn bất kỳ) - Xây dựng mảng original:
- Nếu
derived[i] = 0: phần tử kế tiếp = phần tử hiện tại - Nếu
derived[i] = 1: phần tử kế tiếp = đảo bit hiện tại
- Check điều kiện vòng tròn ở cuối
Intuition của Solution 2
Này là đọc hints là ae nào cũng kiểu BRUHHH =)) lun ....
Phân tích sâu hơn:
derived[0] = original[0] ⊕ original[1]
derived[1] = original[1] ⊕ original[2]
derived[2] = original[2] ⊕ original[3]
...
derived[n-1] = original[n-1] ⊕ original[0]
XOR tất cả lại:
derived[0] ⊕ derived[1] ⊕ ... ⊕ derived[n-1]
= (original[0] ⊕ original[1]) ⊕ (original[1] ⊕ original[2]) ⊕ ... ⊕ (original[n-1] ⊕ original[0])
-> Mỗi phần tử original xuất hiện 2 lần!
-> Do a⊕a = 0, nên tổng XOR phải = 0!Approach 2
- XOR tất cả phần tử trong mảng derived
- Check nếu kết quả = 0
- Bằng 0 -> tồn tại original
- Khác 0 -> không tồn tại original
[Phần Code Implementation và Test Cases giữ nguyên…]
So Sánh Hai Solution
Performance
Solution 1:
✅ Dễ hiểu, trực quan
❌ Tốn O(n) space
❌ Nhiều phép tính hơn
Solution 2:
✅ Elegant, ngắn gọn
✅ Space O(1)
✅ Ít phép tính hơn
❌ Khó giải thích trong interviewKhi Nào Dùng Solution Nào?
- Solution 1: Khi cần giải thích chi tiết trong interview
- Solution 2: Khi cần code tối ưu trong thực tế
Wassup anh em coder! 🌟
Đề bài cho chúng ta:
- Array
derived[]được tạo từ arrayoriginal[]bằng XOR - Mỗi phần tử
derived[i] = original[i] ⊕ original[i+1] - Với phần tử cuối:
derived[n-1] = original[n-1] ⊕ original[0] - Task: Check xem có tồn tại array
originalhợp lệ không
Code Implementation
C++
class Solution {
public:
bool doesValidArrayExist(vector<int>& derived) {
int n = derived.size();
vector<int> orginal(n, 0); // Assume original[0] = 0
int tmp = 0; // Temporary variable to check the cyclic condition
// Derive the original array based on the XOR relationship
for (int i = 0; i < n; i++) {
if (i != n - 1) {
// If derived[i] = 0, the next value in original is the same
if (derived[i] == 0) {
orginal[i + 1] = orginal[i];
} else {
// Otherwise, it's flipped (1 - original[i])
orginal[i + 1] = abs(orginal[i] - 1);
}
} else {
// For the last element, calculate tmp for the cyclic condition
if (derived[i] == 0) {
tmp = orginal[i];
} else {
tmp = abs(orginal[i] - 1);
}
}
}
// Check if the cyclic condition holds
return tmp == orginal[0];
}
};
C++
// Solution 2: XOR Magic
class Solution {
public:
bool doesValidArrayExist(vector<int>& derived) {
int xorSum = 0; // Initialize a variable to store the cumulative XOR of elements in 'derived'
// Iterate through each element in the 'derived' array
for (int x : derived)
xorSum ^= x; // Perform XOR with the current element. This accumulates the XOR of all elements.
// If the cumulative XOR is 0, a valid original array exists. Otherwise, it doesn't.
return xorSum == 0;
}
};
Test Cases & Debug
// Test Case 1:
Input: derived = [1,1,0]
Output: true
Giải thích: original = [0,1,0] hợp lệ
// Test Case 2:
Input: derived = [1,0]
Output: false
Giải thích: Không tồn tại original thỏa mãnComplexity Analysis
Solution 1:
- Time: O(n) - duyệt mảng một lần
- Space: O(n) - tạo mảng original
Solution 2:
- Time: O(n) - duyệt mảng một lần
- Space: O(1) - chỉ dùng 1 biến
Tips & Tricks
- Với bài XOR, luôn nhớ tính chất a⊕a = 0
- Solution đơn giản không có nghĩa là không tối ưu
- Đôi khi cách giải "ngây thơ" lại dễ giải thích hơn trong phỏng vấn
Hy vọng qua bài này anh em đã thêm "công cụ" mới cho arsenal của mình! 🚀
P/S: Đừng quên follow để đón những bài phân tích thú vị tiếp theo nhé! Happy coding! 💻✨
Code Editor
