এই টিউটোরিয়ালে আমরা শিখব কিভাবে Math.sqrt() বা অন্য কোনো ম্যাথ লাইব্রেরি ব্যবহার না করে একটি সংখ্যা পারফেক্ট স্কয়ার কিনা তা চেক করা যায়।
পারফেক্ট স্কয়ার কী?
যেসব সংখ্যা যেকোনো পূর্ণসংখ্যার বর্গ দিয়ে প্রকাশ করা যায়, সেগুলোকে পারফেক্ট স্কয়ার বলে। যেমন: ৪ (২²), ১৬ (৪²), ৮১ (৯²), ৪৪১ (২১²)।
অ্যালগরিদম
১ থেকে শুরু করে প্রতিটি সংখ্যার বর্গ চেক করুন যতক্ষণ না বর্গটি ইনপুট সংখ্যার চেয়ে বড় হয়।
সমাধান
const isPerfectSquare = num => {
// নেগেটিভ সংখ্যা পারফেক্ট স্কয়ার হতে পারে না
if (num < 0) return false;
// ০ এবং ১ পারফেক্ট স্কয়ার
if (num === 0 || num === 1) return true;
let i = 1;
while (i * i <= num) {
if (i * i === num) {
return true; // পারফেক্ট স্কয়ার পাওয়া গেল
}
i++;
}
return false; // কোনো মিল পাওয়া যায়নি
};
// টেস্ট কেস
console.log(isPerfectSquare(81)); // true (9²)
console.log(isPerfectSquare(9801)); // true (99²)
console.log(isPerfectSquare(99)); // false
console.log(isPerfectSquare(441)); // true (21²)
console.log(isPerfectSquare(7648)); // false
অপ্টিমাইজড সংস্করণ (বাইনারি সার্চ)
const isPerfectSquareOptimized = num => {
if (num < 0) return false;
if (num < 2) return true;
let left = 2, right = Math.floor(num / 2);
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const square = mid * mid;
if (square === num) return true;
if (square < num) left = mid + 1;
else right = mid - 1;
}
return false;
};
সময় জটিলতা
- লিনিয়ার: O(√n)
- বাইনারি সার্চ: O(log n) - বড় সংখ্যার জন্য দ্রুত
উৎপাদন
true true false true false
