আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে পূর্ণসংখ্যা রয়েছে। লক্ষ্য হলো এমন সাবঅ্যারে গুলোর সংখ্যা বের করা যাতে প্রতিটি সাবঅ্যারেতে সংলগ্ন (consecutive) উপাদানগুলোর পার্থক্য শুধু ১। উদাহরণস্বরূপ, অ্যারে [1,2,3] হলে সাবঅ্যারে: [1,2], [2,3], [1,2,3]।
উদাহরণ দিয়ে বুঝি
ইনপুট − arr[] = { 4,3,2,1 };
আউটপুট − সংলগ্ন উপাদান ১ অপবদলে সাবঅ্যারে সংখ্যা: ৬
ব্যাখ্যা − সাবঅ্যারে গুলো: [4,3], [3,2], [2,1], [4,3,2], [3,2,1], [4,3,2,1]। মোট ৬।
ইনপুট − arr[] = { 1,5,6,7,9,11 };
আউটপুট − সংলগ্ন উপাদান ১ অপবদলে সাবঅ্যারে সংখ্যা: ৩
ব্যাখ্যা − সাবঅ্যারে গুলো: [5,6], [6,7], [5,6,7]। মোট ৩।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
অ্যারে ট্রাভার্স করি for লুপ দিয়ে। i=0 থেকে i<size। চেক করি কোনো উপাদান তার সংলগ্ন উপাদানের সাথে ১-এ পার্থক্য রাখে কিনা। হ্যাঁ হলে first ইনডেক্স বাড়ান। নহলে সাবঅ্যারের উপাদান সংখ্যা temp = first-last+1। এতে মোট সাবঅ্যারে total = temp*(temp-1)/2। এটাকে count-এ যোগ করুন। first=last=i আপডেট করুন পরবর্তী সেগমেন্টের জন্য।
- অ্যারে
arr[]নিন। sub_ele_diff_one(int arr[], int size)ফাংশন অ্যারে নিয়ে সংলগ্ন উপাদান ১ অপবদলে সাবঅ্যারে কাউন্ট রিটার্ন করে।- প্রাথমিক কাউন্ট ০।
i=1থেকেi<sizeপর্যন্ত লুপে:first,last০ ইনিশিয়ালাইজ করুন।- চেক করুন
arr[i] - arr[i-1] == 1 || arr[i-1] - arr[i] == 1। সত্য হলেfirst++। - অসত্য হলে:
temp = first-last+1,total = temp*(temp-1)/2,count += total,first=i, last=i।
- লুপ শেষে যদি
first != lastহয়, বাকি অংশও প্রসেস করুন। countরিটার্ন করুন।
উদাহরণ
#include <iostream>
using namespace std;
int sub_ele_diff_one(int arr[], int size) {
int count = 0, first = 0, last = 0;
for (int i = 1; i < size; i++) {
if (arr[i] - arr[i - 1] == 1 || arr[i-1] - arr[i] == 1) {
first++;
} else {
int temp = first - last + 1;
int total = temp * (temp - 1) / 2;
count = count + total;
first = i;
last = i;
}
}
if (first != last) {
int temp = first - last + 1;
int total = temp * (temp - 1) / 2;
count = count + total;
}
return count;
}
int main() {
int arr[] = { 1, 2, 4, 3 };
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of Subarrays with Consecutive elements differing by 1 are: " << sub_ele_diff_one(arr, size);
return 0;
}
আউটপুট
Count of Subarrays with Consecutive elements differing by 1 are: 2
