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

हमें एक JavaScript फ़ंक्शन लिखना है जो एकमात्र आर्गुमेंट के रूप में एक धनात्मक संख्या, मान लीजिए num, लेता है।

फ़ंक्शन को ऐसे पूर्ण वर्ग संख्याओं का संयोजन ढूंढना चाहिए जिन्हें जोड़ने पर इनपुट के रूप में दी गई संख्या मिले। हमें यह सुनिश्चित करना है कि हम यथासंभव कम से कम पूर्ण वर्गों का उपयोग करें।

उदाहरण

यदि इनपुट संख्या है:

const num = 123;

तो आउटपुट होना चाहिए:

const output = 3;

क्योंकि 123 = 121 + 1 + 1

यह एक क्लासिक डायनामिक प्रोग्रामिंग समस्या है जहां हम किसी विशेष संख्या के परिणाम तक उसके पूर्ववर्ती संख्याओं के परिणामों के आधार पर पहुंच सकते हैं।

कोड उदाहरण

const num = 123;
const sumSquares = (num) => {
  let arr = new Array(num + 1).fill(0);
  arr[1] = 1;
  for(let i = 1; i * i <= num; i++) {
    for(let j = i * i; j < arr.length; j++) {
      if(arr[j] == 0) {
        arr[j] = arr[j - (i * i)] + 1;
      } else {
        arr[j] = Math.min(arr[j - (i * i)] + 1, arr[j]);
      }
    }
  };
  return arr[num];
};
console.log(sumSquares(num));