এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যার সাইজ N এবং একটি ইন্টিজার মান M। আমাদের কাজ হল অ্যারে থেকে শেষে রিমুভ হওয়া এলিমেন্টের পজিশন বের করা।
অ্যারে থেকে ভ্যালু রিমুভ করার অপারেশনগুলো হল -
- অ্যারেতে একটি এলিমেন্ট arr[i]। যদি arr[i] > M, তবে ভ্যালু পপ করুন এবং arr[i] - M কে অ্যারের শেষে পুশ করুন। অন্যথায় সেটি অ্যারে থেকে রিমুভ করুন।
অপারেশনগুলো ততক্ষণ চলবে যতক্ষণ না অ্যারেতে এলিমেন্ট থাকে।
উদাহরণ দেখি:
ইনপুট
arr[] = {5, 4, 8}, M = 3
আউটপুট
3
ব্যাখ্যা
অপারেশন দিয়ে রিমুভ করলে: {5, 4, 8} -> {4, 8, 2} -> {8, 1, 2} -> {1, 2, 5} -> {2, 5} -> {5} -> {2} -> খালি অ্যারে। শেষে রিমুভ হওয়া ভ্যালু ৮, পজিশন ৩।
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল শেষে রিমুভ হওয়া ভ্যালু বের করার ফ্যাক্ট ব্যবহার করা: প্রতিটি ভ্যালু যা শেষে রিমুভ হবে, তার ceil(arr[i] / M) মান সর্বোচ্চ হবে।
অ্যারে ট্রাভার্স করে ceil(arr[i] / M) এর সর্বোচ্চ মান থাকা এলিমেন্টের পজিশন স্টোর করব।
উদাহরণ
#include <iostream> using namespace std; int findLastRemPos(int arr[], int n, int m){ for (int i = 0; i < n; i++) { arr[i] = (arr[i] / m + (arr[i] % m != 0)); } int lastRemPos = -1, largestVal = -1; for (int i = n - 1; i >= 0; i--) { if (largestVal < arr[i]) { largestVal = arr[i]; lastRemPos = i; } } return lastRemPos + 1; } int main(){ int arr[] = {5, 4, 8, 1}; int n = sizeof(arr) / sizeof(arr[0]); int m = 3; cout<<"The position of last removed element in the array is "<<findLastRemPos(arr, n, m); return 0; }
আউটপুট
The position of last removed element in the array is 3
