हमें एक जावास्क्रिप्ट फ़ंक्शन लिखने की आवश्यकता है जो एक सकारात्मक संख्या लेता है, जैसे कि संख्या, एकमात्र तर्क के रूप में।
फ़ंक्शन को ऐसे पूर्ण वर्ग संख्याओं का संयोजन खोजना चाहिए जो जोड़ने पर इनपुट के रूप में प्रदान की गई संख्या देता है। हमें यह सुनिश्चित करना होगा कि हम पूर्ण वर्गों की यथासंभव कम संख्या का उपयोग करें।
उदाहरण के लिए -
अगर इनपुट नंबर है -
const num = 123;
तब आउटपुट होना चाहिए -
const output = 3;
क्योंकि 123 =121 + 1 + 1
यह एक क्लासिक डायनेमिक प्रोग्रामिंग समस्या है जहां हम किसी विशेष संख्या के लिए उसके पूर्ववर्ती नंबरों के परिणामों के आधार पर परिणाम तक पहुंच सकते हैं।
सीधे कोड में जाने से पहले आइए पहले एक सामान्य पैटर्न को समझने की कोशिश करें और डीपी वास्तव में समाधान तैयार करने में हमारी मदद कैसे करेगा।
छह पांच नंबरों का परिणाम होगा -
1 --> 1 (1) 2 --> 2 (1 + 1) 3 --> 3 (1 + 1 + 1) 4 --> 1 (4) 5 --> 2 (4 + 1) 6 --> 3 (4 + 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)); आउटपुट
कंसोल आउटपुट निम्नलिखित है -
3