By Loser1 from Learning AI with Loser

Input: n = 10
Output: 182
Giải thích: 
Có đúng 3 số nguyên i trong khoảng [1, 10] thỏa mãn điều kiện:
- 1 vì 1 * 1 = 1
- 9 vì 9 * 9 = 81 và 81 có thể được chia thành 8 và 1 với tổng bằng 8 + 1 == 9.
- 10 vì 10 * 10 = 100 và 100 có thể được chia thành 10 và 0 với tổng bằng 10 + 0 == 10.
Do đó, số phạt của 10 là 1 + 81 + 100 = 182.
    

Input: n = 37
Output: 1478
Giải thích: 
Có đúng 4 số nguyên i trong khoảng [1, 37] thỏa mãn điều kiện:
- 1 vì 1 * 1 = 1.
- 9 vì 9 * 9 = 81 và 81 có thể được chia thành 8 + 1.
- 10 vì 10 * 10 = 100 và 100 có thể được chia thành 10 + 0.
- 36 vì 36 * 36 = 1296 và 1296 có thể được chia thành 1 + 29 + 6.
Do đó, số phạt của 37 là 1 + 81 + 100 + 1296 = 1478.
    

👋 Xin chào mọi người, mình là Loser1 from Learning AI With Losers! 🚀

Hôm nay là Day 37 trong thử thách Leetcode Daily Challenge, và chúng ta sẽ khám phá một bài toán thú vị liên quan đến chia nhỏ một số bình phương thành các phần có tổng bằng chính nó! 🤯

🎯 Problem Statement

Cho một số nguyên n, nhiệm vụ của chúng ta là tìm Punishment Number của n.

Punishment Number của n được định nghĩa như sau:

👉 Tổng bình phương của tất cả các số i (1 ≤ i ≤ n) thỏa mãn điều kiện:
✅ i² có thể chia thành các phần liên tiếp, sao cho tổng của chúng bằng i.

💡 Ví dụ minh họa

Example 1

Input: n = 10  
Output: 182  

Giải thích:

Các số thỏa mãn điều kiện:

• 1: 1² = 1 → có thể giữ nguyên (✅)
• 9: 9² = 81 → chia thành 8 + 1 = 9 (✅)
• 10: 10² = 100 → chia thành 10 + 0 = 10 (✅)

👉 Punishment Number = 1² + 9² + 10² = 1 + 81 + 100 = 182 🎯

Example 2

Input: n = 37  
Output: 1478  

Giải thích:

Các số thỏa mãn điều kiện:

• 1: 1² = 1 → có thể giữ nguyên (✅)
• 9: 9² = 81 → chia thành 8 + 1 = 9 (✅)
• 10: 10² = 100 → chia thành 10 + 0 = 10 (✅)
• 36: 36² = 1296 → có thể chia thành 1 + 29 + 6 = 36 (✅)

👉 Punishment Number = 1² + 9² + 10² + 36² = 1 + 81 + 100 + 1296 = 1478 🎯

🔍 Example Walkthrough - Phân tích chi tiết

Để hiểu rõ hơn cách kiểm tra số nào hợp lệ, hãy cùng đi sâu vào một số ví dụ cụ thể.

📌 Case 1: i = 9

Ta kiểm tra xem 9² = 81 có thể phân chia thành các phần nhỏ sao cho tổng bằng 9 hay không?

  81  
 /  \  
8   1  → 8 + 1 = 9 ✅ (Thoả mãn)

⏳ Kết luận: 9 là số hợp lệ!

📌 Case 2: i = 10

Ta kiểm tra xem 10² = 100 có thể phân chia thành các phần nhỏ sao cho tổng bằng 10 hay không?

  100  
 /    \  
10     0  → 10 + 0 = 10 ✅ (Thoả mãn)

⏳ Kết luận: 10 là số hợp lệ!

📌 Case 3: i = 36

Ta kiểm tra xem 36² = 1296 có thể phân chia thành các phần nhỏ sao cho tổng bằng 36 hay không?

1296  
│  
├── "1" → 296  
│      ├── "2" → 96  
│      │      ├── "9" → 6 ✅  
│      │      └── "96" ❌  
│      └── "29" → 6 ✅  
└── "12" → 96 ❌  

Như bạn thấy, cách phân chia "1" → "29" → "6" giúp ta đạt tổng 36, vì 1 + 29 + 6 = 36.

⏳ Kết luận: 36 là số hợp lệ!

🚀 Approach - How to Solve the Problem?

📌 Bước 1: Kiểm tra một số i có hợp lệ hay không?

Ta cần kiểm tra xem i² có thể phân chia thành các phần có tổng bằng i không.

💡 Ý tưởng của hàm đệ quy (isValidPartition):

• Chia num thành các phần số từ trái sang phải bằng vòng for.
• Dùng đệ quy để kiểm tra các phần còn lại của chuỗi.
• Nếu tìm được một cách chia hợp lệ, ta trả về true.

📌 Bước 2: Tính Punishment Number

• Duyệt từng i từ 1 đến n.
• Nếu i hợp lệ (thỏa mãn điều kiện trên), cộng i² vào tổng.

⏳ Complexity Analysis

• Time Complexity: O(n⋅2d)O(n \cdot 2^d) với d là số chữ số của i² (do mỗi chữ số có thể có hoặc không trong một phần).
• Space Complexity: O(d)O(d) do độ sâu của stack đệ quy.

💻 Code Implementation

class Solution {
public:
    // Hàm đệ quy kiểm tra xem có thể chia num thành các phần có tổng bằng target không
    bool isValidPartition(string &num, int target, int start, int sum) {
        if (start == num.size()) return sum == target; // Nếu đã xét hết chuỗi, kiểm tra tổng
        
        int currNum = 0;
        for (int i = start; i < num.size(); i++) {
            currNum = currNum * 10 + (num[i] - '0'); // Chuyển đổi từng phần tử thành số nguyên
            
            if (isValidPartition(num, target, i + 1, sum + currNum)) {
                return true; // Nếu có một cách chia hợp lệ, return true ngay
            }
        }
        
        return false;
    }

    // Hàm kiểm tra xem số i có thoả mãn điều kiện không
    bool check(int i) {
        string sq_str = to_string(i * i); // Chuyển bình phương thành chuỗi
        return isValidPartition(sq_str, i, 0, 0); // Kiểm tra tất cả các cách chia
    }

    // Hàm tính punishment number
    int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (check(i)) {
                ans += i * i; // Nếu thoả mãn điều kiện, cộng bình phương vào tổng
            }
        }
        return ans;
    }
};

🏅 Final Thoughts

Bài toán này kết hợp giữa chuỗi, đệ quy, backtracking và toán học. 🚀
Bạn đã làm được bài này chưa? Comment bên dưới để mình biết nhé! ⬇️🔥

📢 Leetcode Daily Challenge - Day 37 hoàn thành! 🚀
💙 Nếu bạn thích bài viết này, hãy theo dõi Learning AI With Losers để không bỏ lỡ bất kỳ bài phân tích nào nhé!
📌 Hẹn gặp lại trong Day 38! 🚀

👉 Stay tuned & Keep grinding! 💪

CODE EDITOR

📌 Hashtags:
#leetcode #leetcodedaily #coding #datastructures #algorithms #learningwithlosers #leetcode 3066 # leetcodedaily37