এই সমস্যায়, আমাদের একটি অ্যারে aar[] দেওয়া আছে n সংখ্যক ইন্টিজার মান দিয়ে যা সর্টেড নয় এবং একটি ইন্টিজার val। আমাদের কাজ হল আনসর্টেড অ্যারেতে একটি উপাদানের শুরু ও শেষ ইনডেক্স খুঁজে বের করা।
উপাদানটি অ্যারেতে কতবার আছে তার উপর ভিত্তি করে আমরা রিটার্ন করব:
- "Starting index and ending index" যদি অ্যারেতে দুইবার বা তার বেশি থাকে।
- "Single index" যদি অ্যারেতে একবার থাকে।
- "Element not present" যদি অ্যারেতে না থাকে।
উদাহরণ ১
ইনপুট : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 2
আউটপুট : starting index = 0, ending index = 5
ব্যাখ্যা:
উপাদান 2-এর দুটি ঘটনা:
প্রথমটি ইনডেক্স = 0-এ,
দ্বিতীয়টি ইনডেক্স = 5-এ
উদাহরণ ২
ইনপুট : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 5
আউটপুট : Present only once at index 2
ব্যাখ্যা:
উপাদান 5-এর একমাত্র ঘটনা, ইনডেক্স = 2-এ
উদাহরণ ৩
ইনপুট : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 7
আউটপুট : Not present in the array!
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হল অ্যারে ট্রাভার্স করা।
আমরা অ্যারে ট্রাভার্স করব এবং দুটি ইনডেক্স মান রাখব, first এবং last। First ইনডেক্স অ্যারেটি শুরু থেকে ট্রাভার্স করবে এবং last ইনডেক্স শেষ থেকে। এবং লুপটি শেষ করব যখন first এবং last ইনডেক্সের উপাদানের মান একই হয়ে যায়।
অ্যালগরিদম
স্টেপ ১ − অ্যারে ট্রাভার্স করুন
স্টেপ ১.১ − শুরু থেকে ট্রাভার্স করার জন্য first ইনডেক্স এবং শেষ থেকে ট্রাভার্স করার জন্য last ইনডেক্স ব্যবহার করুন।
স্টেপ ১.২ − যদি যেকোনো ইনডেক্সের মান val-এর সমান হয়, তবে ইনডেক্স মান বাড়ান না।
স্টেপ ১.৩ − যদি দুটি ইনডেক্সের মান একই হয়, রিটার্ন করুন।
উদাহরণ প্রোগ্রাম
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#include <iostream>
using namespace std;
void findStartAndEndIndex(int arr[], int n, int val) {
int start = 0;
int end = n - 1;
while (1) {
if (arr[start] != val)
start++;
if (arr[end] != val)
end--;
if (arr[start] == arr[end] && arr[start] == val)
break;
if (start == end)
break;
}
if (start == end) {
if (arr[start] == val)
cout << "Element is present only once at index : " << start;
else
cout << "Element Not Present in the array";
} else {
cout << "Element present twice at \n";
cout << "Start index: " << start << endl;
cout << "Last index: " << end;
}
}
int main() {
int arr[] = { 2, 1, 5, 4, 6, 2, 9, 0, 2, 3, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int val = 2;
findStartAndEndIndex(arr, n, val);
return 0;
}
আউটপুট
Element present twice at Start index: 0 Last index: 8
