โปรแกรมนับจำนวนกำลังสองน้อยที่สุดที่รวมกันได้ N ใน C++

ภาพรวมปัญหา

ให้จำนวนเต็มบวก n ต้องการหาจำนวนกำลังสองน้อยที่สุดที่รวมกันได้ n (Perfect Squares Sum)

ตัวอย่าง

Input: n = 10

Output: 2

คำอธิบาย: 10 = 9 + 1 = 3² + 1²

ทฤษฎีทางคณิตศาสตร์ (Lagrange's Four Square Theorem)

ทุกจำนวนเต็มบวกสามารถเขียนเป็นผลรวมของกำลังสองได้ไม่เกิน 4 ตัว

คำตอบจะเป็น 1, 2, 3, หรือ 4 เท่านั้น

แนวทาง Dynamic Programming

1. dp[i] = จำนวนกำลังสองน้อยที่สุดที่รวมได้ i
2. dp[0] = 0
3. สำหรับ i = 1..n: dp[i] = min(dp[i], 1 + dp[i - j²]) สำหรับทุก j ที่ j² ≤ i

โค้ดตัวอย่าง (DP)

#include <bits/stdc++.h>
using namespace std;

#define INF 1e9

class Solution {
public:
    int solve(int n) {
        vector dp(n + 1, INF);
        dp[0] = 0;
        
        for (int i = 1; i * i <= n; i++) {
            int sq = i * i;
            for (int j = sq; j <= n; j++) {
                dp[j] = min(dp[j], 1 + dp[j - sq]);
            }
        }
        return dp[n];
    }
};

int main() {
    Solution ob;
    cout << ob.solve(10);
    return 0;
}

ผลลัพธ์

2

แนวทางทางคณิตศาสตร์ O(√N) — เร็วกว่า DP มาก

ใช้ทฤษฎี Lagrange และ Legendre's Three-Square Theorem:

1. ถ้า n เป็นกำลังสอง → คืน 1
2. ลบ 4ᵏ ออกจาก n จนไม่หาร 4 ลงตัว (n = 4ᵏ × m)
3. ถ้า m % 8 == 7 → คืน 4 (ต้องใช้ 4 ตัว)
4. ตรวจสอบว่า n = a² + b² ได้ไหม → ถ้าได้คืน 2
5. มิฉะนั้น คืน 3

โค้ด Mathematical O(√N)

int numSquares_math(int n) {
    // Check 1: perfect square
    int sq = sqrt(n);
    if (sq * sq == n) return 1;
    
    // Check 4: Legendre's condition
    int m = n;
    while (m % 4 == 0) m /= 4;
    if (m % 8 == 7) return 4;
    
    // Check 2: sum of two squares
    for (int i = 1; i * i <= n; i++) {
        int rem = n - i * i;
        int r = sqrt(rem);
        if (r * r == rem) return 2;
    }
    
    // Otherwise 3
    return 3;
}

ความซับซ้อน

หมายเหตุ

DP ใช้ได้กับ n ≤ 10⁴-10⁵, Mathematical ใช้ได้กับ n ≤ 10⁹+

ปัญหานี้คือ LeetCode 279 "Perfect Squares"

โปรแกรมคำนวณนิพจน์ Postfix (Reverse Polish Notation) ใน C++

โปรแกรมรวมต้นไม้ไบนารีสองต้นใน C++