এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে প্রতিটি উপাদান বাক্সের কুঁড়ে রিপ্রেজেন্ট করে (প্রতিটি ইউনিট হাইট)। আমাদের কাজ হল বাদ দেওয়া বাক্সের সংখ্যা বের করা।
ব্যক্তিটি অ্যারেতার ইনডেক্স ০-এ দাঁড়িয়ে আছে বাক্সের কুঁড়ের হাইটে এবং তাকে অ্যারেতার শেষে যেতে হবে। এক কুঁড়ে থেকে পরের কুঁড়ে যাওয়ার শর্ত হল পরবর্তী কুঁড়ে যাম্প দেওয়া।
যাম্প শুধু তখন সম্ভব যখন পরের কুঁড়ে একই হাইটে থাকে বা তার হাইট কম থাকে। যদি পরের কুঁড়ের হাইট বেশি হয়, তবে ব্যক্তিটি পরের কুঁড় থেকে বাক্স বাদ দিবে যতক্ষণ না হাইট সমান হয়। আমাদের প্রথম কুঁড় থেকে শেষ কুঁড় পর্যন্ত যাওয়ার সময় মোট কতগুলো বাক্স বাদ দেওয়া হবে সেটি বের করতে হবে।
উদাহরণ
সমস্যাটি বুঝতে একটি উদাহরণ নিই:
ইনপুট : arr[] = {5, 7, 3, 1, 2}
আউটপুট : 3
ব্যাখ্যা
প্রাথমিক অবস্থায়, ব্যক্তিটি হাইট ৫-এ আছে।
স্টেপ ১ − দ্বিতীয় পজিশনে যাওয়ার জন্য যাতে ৭ হাইট আছে, ব্যক্তিটি ২টি বাক্স বাদ দেবে।
স্টেপ ২ − তৃতীয় পজিশনে যাওয়ার জন্য যাতে ৩ হাইট আছে, কোনো বাক্স বাদ দিতে হয় না।
স্টেপ ৩ − পরবর্তী পজিশনে যাওয়ার জন্য যাতে ১ হাইট আছে, কোনো বাক্স বাদ দিতে হয় না।
স্টেপ ৪ − পরবর্তী পজিশনে যাওয়ার জন্য যাতে ২ হাইট আছে, ১টি বাক্স বাদ দিতে হয়। এতে মোট বাদ দেওয়া বাক্সের সংখ্যা ৩ হয়।
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হল অ্যারে শুরু থেকে শেষ পর্যন্ত ট্রাভার্স করা এবং চেক করা পরের উপাদানটি বর্তমানটি থেকে বড় কি না। যদি হয়, তবে তাদের পার্থক্যকে boxesRemoved ভেরিয়েবলে যোগ করব যেটি মোট বাদ দেওয়া বাক্সের সংখ্যা ধারণ করে। শেষে আমরা boxesRemoved রিটার্ন করব।
উদাহরণ প্রোগ্রাম
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#include <iostream>
using namespace std;
int findBoxesRemoved(int arr[], int n) {
int boxesRemoved = 0;
for (int i = 0; i < n - 1; i++) {
if (arr[i] < arr[i + 1])
boxesRemoved += (arr[i + 1] - arr[i]);
}
return boxesRemoved;
}
int main() {
int arr[] = { 5, 7, 3, 1, 2, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The total number of boxes to be removed to reach the end is " << findBoxesRemoved(arr, n);
return 0;
}
আউটপুট
The total number of boxes to be removed to reach the end is 7
