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

Hôm nay chúng ta sẽ cùng nhau khám phá một bài toán thú vị về việca tìm các cặp số có cùng tích! Let’s dive in! 🎭

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valid tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

🔥 First Thoughts & Intuition

Hãy tưởng tượng bạn đang ghép đôi các con số:

Ví dụ với [2,3,4,6]:
2 × 6 = 12
3 × 4 = 12

Giống như một điệu nhảy, các số có thể hoán đổi vị trí:
(2,6) (3,4)
⬇️ ⬇️
(3,4) (2,6)

💡 Approach

1. Cặp Đôi Hoàn Hảo 💑

Bước 1: Tìm các cặp có cùng tích
(2,6) = 12
(3,4) = 12

Bước 2: Đếm số cách hoán đổi

• (2,6,3,4)
• (2,6,4,3)
• (6,2,3,4)
  …và còn nữa!

2. Công Thức Tính Nhanh ⚡

Với mỗi tích xuất hiện f lần:

• Chọn 2 cặp từ f cặp: C(f,2)
• Mỗi cặp có thể xoay 8 cách
• Tổng = 8 × C(f,2)

🎯 Visualization Examples

Ví dụ 1: [2,3,4,6]

Bước 1: Tạo Map
2×3 = 6 [1 lần]
2×4 = 8 [1 lần]
2×6 = 12 [1 lần]
3×4 = 12 [1 lần]
3×6 = 18 [1 lần]
4×6 = 24 [1 lần]

Bước 2: Tìm Tích Chung
12 xuất hiện 2 lần:

• 2×6 = 12
• 3×4 = 12

Bước 3: Tính Kết Quả

• 8 cách sắp xếp

🚀 Implementation

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        unordered_map<int, int> productCount;
        int n = nums.size();

        // Tính tích các cặp
        for(int i = 0; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                productCount[nums[i] * nums[j]]++;
            }
        }

        int result = 0;
        // Tính số tuple
        for(auto &[product, count] : productCount) {
            if(count >= 2) {
                result += count * (count-1) * 4; // 8 * C(count,2)
            }
        }

        return result;
    }
};

📊 Complexity Analysis

Time: O(N²)

For loop:
🔄 Duyệt tất cả cặp số
⏱️ N×(N-1)/2 phép tính

Space: O(N²)

HashMap:
📦 Lưu trữ các tích
🗃️ Tối đa N×(N-1)/2 tích khác nhau

💎 Key Insights

1. 🎯 Pattern Recognition:

• Tìm cặp có cùng tích
• Đếm số cách sắp xếp

1. 🧮 Math is Beautiful:

• Combination C(n,2)
• Permutation của cặp số

1. 🚀 Optimization Tips:

• Dùng HashMap để đếm nhanh
• Early return khi count < 2

Hi vọng bài viết này giúp các bạn hiểu rõ hơn về cách xử lý bài toán tuple! Hẹn gặp lại trong những bài tiếp theo! 🎉

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 #tuples #codinglife