আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি ধনাত্মক সংখ্যা (num) একমাত্র আর্গুমেন্ট হিসেবে গ্রহণ করবে।
ফাংশনটি এমন পারফেক্ট স্কয়ার সংখ্যাগুলোর সমষ্টি খুঁজে বের করবে যারা যোগ করলে num হয়। এবং এতে যতসম্ভব কম সংখ্যক পারফেক্ট স্কয়ার ব্যবহার করতে হবে।
উদাহরণস্বরূপ —
ইনপুট সংখ্যা যদি হয় —
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
