Minimum Number of Squares Sum to n (ทฤษฎี Lagrange's Four Square)

ทุกจำนวนเต็มบวกสามารถเขียนเป็นผลรวมของจำนวนกำลังสอง (Perfect Squares) ได้ ต้องการหา จำนวนพจน์น้อยที่สุด ที่จำเป็น

ตัวอย่าง Input และ Output

Input: 63
Output: Minimum Squared Term needed: 4
63 = 7² + 3² + 2² + 1² = 49 + 9 + 4 + 1

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

• ทุกจำนวนธรรมชาติ = ผลรวมของสูงสุด 4 จำนวนกำลังสอง
• Legendre's Three-Square Theorem: n ต้องการ 4 squares ก็ต่อเมื่อ n = 4ᵃ(8b+7)

อัลกอริทึม Dynamic Programming

ฟังก์ชัน minSquareTerms(value)

Recurrence:

sqList[i] = min over x (1 + sqList[i - x²]) สำหรับ x = 1, 2, ... จนกว่า x² > i

ขั้นตอน:

1. sqList[0]=0, sqList[1]=1, sqList[2]=2, sqList[3]=3
2. for i = 4 ถึง n:
   • sqList[i] = i (worst case: 1² + 1² + ...)
   • for x = 1; x² ≤ i; x++:
     • sqList[i] = min(sqList[i], 1 + sqList[i - x²])
3. คืน sqList[n]

ตัวอย่างโค้ด C++

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int minSquareTerms(int n) {
    int *squareList = new int[n+1];
    squareList[0] = 0;
    squareList[1] = 1;
    squareList[2] = 2;
    squareList[3] = 3;

    for (int i = 4; i <= n; i++) {
        squareList[i] = i; // worst case: all 1's
        for (int x = 1; x*x <= i; x++) {
            squareList[i] = min(squareList[i], 1 + squareList[i - x*x]);
        }
    }
    int result = squareList[n];
    delete[] squareList;
    return result;
}

int main() {
    int n;
    cout << "Enter a number: "; cin >> n;
    cout << "Minimum Squared Term needed: " << minSquareTerms(n);
    return 0;
}

Output

Enter a number: 63
Minimum Squared Term needed: 4

ความซับซ้อน

• Time: O(n√n) ≈ O(n¹·⁵)
• Space: O(n)

วิธี O(1) ด้วยทฤษฎี (Mathematical Approach)

int minSquaresMath(int n) {
    // ตรวจสอบ 1 square
    if (isPerfectSquare(n)) return 1;
    
    // ตรวจสอบ 2 squares
    for (int i = 1; i*i <= n; i++)
        if (isPerfectSquare(n - i*i)) return 2;
    
    // ตรวจสอบ 4 squares (Legendre's condition)
    int m = n;
    while (m % 4 == 0) m /= 4;
    if (m % 8 == 7) return 4;
    
    // ไม่ใช่ 1, 2, 4 → ต้องเป็น 3
    return 3;
}

วิธีนี้เร็วกว่ามากสำหรับ n ใหญ่