दी गई संख्या n के बराबर योग वाले वर्गों की न्यूनतम संख्या

किसी भी संख्या को कुछ पूर्ण वर्ग संख्याओं के योग द्वारा दर्शाया जा सकता है। इस समस्या में, हमें यह ढूंढना है कि दी गई मान को दर्शाने के लिए न्यूनतम कितने पूर्ण वर्ग पदों की आवश्यकता है।

मान लें मान 94 है, तो 95 = 9² + 3² + 2² + 1²। तो उत्तर 4 होगा।

विचार 1 से शुरू करना है, हम पूर्ण वर्ग संख्याएं प्राप्त करने के लिए आगे बढ़ते हैं। जब मान 1 से 3 होता है, तो उन्हें केवल 1s से बनाया जाना चाहिए।

इनपुट और आउटपुट

इनपुट: एक पूर्णांक संख्या। मान लें 63।
आउटपुट: वर्ग पदों की संख्या। यहां उत्तर 4 है।
63 = 7² + 3² + 2² + 1

एल्गोरिदम

minSquareTerms(value)

इनपुट: दिया गया मान
आउटपुट: दिए गए मान तक पहुंचने के लिए न्यूनतम वर्ग पदों की संख्या

शुरुआत
    sqList ऐरे को आकार value + 1 का परिभाषित करें
    sqList[0] := 0, sqList[1] := 1, sqList[2] := 2, sqList[3] := 3
    i रेंज 4 से n में, करें
        sqList[i] := i
        x := 1 से i तक, करें
            temp := x²
            यदि temp > i, तो
                लूप तोड़ें
            अन्यथा sqList[i] := sqList[i] और (1 + sqList[i-temp]) का न्यूनतम
        पूर्ण
    पूर्ण
    वापस sqList[n]
अंत

उदाहरण (C++ कोड)

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

int min(int x, int y) {
    return (x < y) ? x : y;
}

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;
        for (int x = 1; x <= i; x++) {
            int temp = x*x;
            if (temp > i)
                break;
            else
                squareList[i] = min(squareList[i], 1 + squareList[i-temp]);
        }
    }
    return squareList[n];
}

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

आउटपुट

Enter a number: 63
Minimum Squared Term needed: 4