Xin chào các bạn yêu quý của Learning AI With Losers! Mình là Loser1 đây!

Mùng 4 Tết Ất Tỵ 2025 – ngày cuối cùng của kỳ nghỉ Tết, chúng ta sẽ cùng nhau khám phá một bài toán thú vị về tính “đặc biệt” của một mảng số! Let’s dive in! 🎊

Input: nums = [1]
Output: true
Explanation:
Chỉ có một phần tử. Vì vậy, kết quả là true.

Input: nums = [2,1,4]
Output: true
Explanation:
Chỉ có hai cặp: (2,1) và (1,4), và cả hai đều chứa các số có tính chẵn lẻ khác nhau. Vì vậy, kết quả là true.

Input: nums = [4,3,1,6]
Output: false
Explanation:
nums[1] và nums[2] đều là số lẻ. Vì vậy, kết quả là false.

📝 Problem Statement

Một mảng được gọi là "đặc biệt" (special) khi mọi cặp số liền kề đều có tính chất chẵn-lẻ khác nhau. Nhiệm vụ của chúng ta là kiểm tra xem một mảng cho trước có phải là mảng đặc biệt hay không.

🔥 First Thoughts & Intuition

Hãy tưởng tượng mảng số như một điệu nhảy! 💃🕺

Điệu nhảy đúng (Valid Dance):
🟢(1) ➡️ 🔵(2) ➡️ 🟢(3) ➡️ 🔵(4)
(Lẻ) (Chẵn) (Lẻ) (Chẵn)

Điệu nhảy sai (Invalid Dance):
🔵(2) ➡️ 🔵(4) ➡️ 🔵(6)
(Chẵn) (Chẵn) (Chẵn)

Quy luật đơn giản:

• 🔵 (Chẵn) phải nhảy với 🟢 (Lẻ)
• 🟢 (Lẻ) phải nhảy với 🔵 (Chẵn)
• Không được có hai số cùng màu đứng cạnh nhau!

💡 Approach

1. Visual Pattern Recognition 👀

Các pattern hợp lệ:

Pattern 1: Chẵn-Lẻ-Chẵn
🔵2️⃣ ➡️ 🟢3️⃣ ➡️ 🔵4️⃣
✅ Perfect!

Pattern 2: Lẻ-Chẵn-Lẻ
🟢1️⃣ ➡️ 🔵2️⃣ ➡️ 🟢3️⃣
✅ Perfect!

Các pattern không hợp lệ:

Pattern 3: Chẵn-Chẵn
🔵2️⃣ ➡️ 🔵4️⃣
❌ Same parity!

Pattern 4: Lẻ-Lẻ
🟢3️⃣ ➡️ 🟢5️⃣
❌ Same parity!

2. Bitwise Magic 🎩

Cách check số chẵn/lẻ siêu tốc với bitwise:

Số chẵn (Even):
6 = 110₂
1 = 001₂
6 & 1 = 0 ✨

Số lẻ (Odd):
5 = 101₂
1 = 001₂
5 & 1 = 1 ✨

3. Dancing Partners Check 💃🕺

Step-by-step process:

1. Kiểm tra số phần tử

• 1 phần tử: ✅ Luôn đúng
• 2+ phần tử: Cần check từng cặp

1. Với mỗi cặp số:
   Partner 1 Partner 2 Result
   🟢(1) ➡️ 🔵(2) ✅
   🔵(2) ➡️ 🟢(3) ✅
   🟢(3) ➡️ 🔵(4) ✅
2. Quy tắc kiểm tra:
   if((nums[i] & 1) == (nums[i+1] & 1))
   → Cùng tính chất = Sai ❌
   → Khác tính chất = Đúng ✅

🚀 Implementation

class Solution {
public:
    bool isArraySpecial(vector<int>& nums) {
        // Case 1: Single element
        if(nums.size() == 1) return true;  

        // Case 2: Check each adjacent pair
        for(int i = 0; i < nums.size() - 1; i++) {
            // If same parity → Not special
            if((nums[i] & 1) == (nums[i + 1] & 1)) {
                return false;
            }
        }

        // All pairs passed → Special array!
        return true;
    }
};

🎯 Example Walkthrough

Example 1: Perfect Dance

Input: [1, 2, 3, 4]

Step-by-step:
1️⃣ Check (1,2):
1 & 1 = 1 (Lẻ)
2 & 1 = 0 (Chẵn)
1 ≠ 0 ✅

2️⃣ Check (2,3):
2 & 1 = 0 (Chẵn)
3 & 1 = 1 (Lẻ)
0 ≠ 1 ✅

3️⃣ Check (3,4):
3 & 1 = 1 (Lẻ)
4 & 1 = 0 (Chẵn)
1 ≠ 0 ✅

Result: true ✨

Example 2: Failed Dance

Input: [2, 4, 6]

Step-by-step:
1️⃣ Check (2,4):
2 & 1 = 0 (Chẵn)
4 & 1 = 0 (Chẵn)
0 = 0 ❌

Result: false 💔

Example 3: Solo Dance

Input: [7]

Step-by-step:
1️⃣ Single element → true ✅

📊 Complexity Analysis

Time Complexity: O(N)

Visualization:
[1] → [2] → [3] → [4] → [5]
↓ ↓ ↓ ↓ ↓
Check Check Check Check Done!

🔍 One pass through array
⏱️ Linear time with size

Space Complexity: O(1)

🧠 Variables used:

• Loop counter (i)
• Current pair comparison

📦 No extra space needed!

💎 Advanced Tips & Tricks

1. Early Exit Strategy 🚪

   if(nums.size() == 1) return true;

• Tránh việc check không cần thiết
• Tối ưu performance

1. Bitwise Over Modulo ⚡

   // Slower
   if(nums[i] % 2 == nums[i+1] % 2)

   // Faster
   if((nums[i] & 1) == (nums[i+1] & 1))

3. Loop Optimization 🔄

   // No need for extra vars
   for(int i = 0; i < nums.size() - 1; i++)

🎉 Conclusion

Bài toán Special Array I tuy là bài Easy nhưng cho chúng ta thấy:

• Tầm quan trọng của bitwise operations
• Cách tối ưu hóa code đơn giản nhưng hiệu quả
• Pattern recognition trong array problems

Chúc mừng năm mới 2025! Hi vọng bài Easy đầu tiên trong series sẽ mang lại nhiều điều tốt đẹp! 🎊

Follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 💻✨

CODE EDITOR

#leetcode #leetcodedaily #algorithms #programming #learningwithlosers #newyear2025 #tetholidaycoding