এই সমস্যাতে, আমাদের একটি সংখ্যা N দেওয়া আছে যা ইটের সংখ্যা নির্দেশ করে সিঁড়ি তৈরি করতে। আমাদের কাজ হল সিঁড়ির ধাপের সংখ্যা বের করা।
দেওয়া ইট দিয়ে সিঁড়ির ধাপ তৈরি করতে হবে। প্রতিটি ধাপে পূর্বের ধাপের চেয়ে একটি বেশি ইট লাগে। এবং প্রথম ধাপে ২টি ইট লাগে। এমন ধাপ কতগুলো তৈরি করা যায় সেটি বের করতে হবে।
উদাহরণ দেখি:
ইনপুট
N = 40
আউটপুট
3
ব্যাখ্যা
ধাপ = ১; প্রয়োজনীয় ইট = ২; ব্যবহৃত ইট = ২; বাকি ইট = ৩৮
ধাপ = ২; প্রয়োজনীয় ইট = ৩; ব্যবহৃত ইট = ৫; বাকি ইট = ৩৫
ধাপ = ৩; প্রয়োজনীয় ইট = ৪; ব্যবহৃত ইট = ৯; বাকি ইট = ৩১
ধাপ = ৪; প্রয়োজনীয় ইট = ৫; ব্যবহৃত ইট = ১৪; বাকি ইট = ২৬
ধাপ = ৫; প্রয়োজনীয় ইট = ৬; ব্যবহৃত ইট = ২০; বাকি ইট = ২০
ধাপ = ৬; প্রয়োজনীয় ইট = ৭; ব্যবহৃত ইট = ২৭; বাকি ইট = ১৩
ধাপ = ৭; প্রয়োজনীয় ইট = ৮; ব্যবহৃত ইট = ৩৫; বাকি ইট = ৫
আর কোনো ধাপ তৈরি করা যায় না কারণ ৮ম ধাপে ৯টি ইট লাগবে কিন্তু আছে শুধু ৫টি।
সমাধানের পদ্ধতি
একটি সহজ পদ্ধতি হল লুপ ব্যবহার করা, ২ থেকে শুরু করে যতক্ষণ না ব্যবহৃত ইট N-এর চেয়ে বড় হয়। তারপর শেষ ধাপের কাউন্ট রিটার্ন করা।
এই সমাধানটি ভালো কিন্তু টাইম কমপ্লেক্সিটি O(N)। আরও ভালো পদ্ধতি হল যোগফলের ফর্মুলা এবং বাইনারি সার্চ ব্যবহার করা।
আমাদের কাছে X আছে যা মোট ব্যবহৃত ইটের সংখ্যা যা সবসময় (n*(n+1))/2 থেকে বড় হয় কারণ আমাদের সব ধাপের ইটের যোগফল থাকে। এই ক্ষেত্রে সমাধান হবে মিড এবং মিড-১ এই দুটি মান থেকে যেকোনো একটি।
উদাহরণ
#include <iostream> using namespace std; int findStairCount(int T){ int low = 1; int high = T/2; while (low <= high) { int mid = (low + high) / 2; if ((mid * (mid + 1)) == T) return mid; if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T) return mid - 1; if ((mid * (mid + 1)) > T) high = mid - 1; else low = mid + 1; } return -1; } int main(){ int N = 60; int stepCount = findStairCount(2*N); if (stepCount != -1) stepCount--; cout<<"The number of stair steps that can be made is "<<stepCount; return 0; }
আউটপুট
The number of stair steps that can be made is 9
