একটি অ্যারে arr[N] দেওয়া আছে। অ্যারেটি বিটোনিক কিনা তা যাচাই করতে হবে। বিটোনিক হলে "Yes its a bitonic array", নাহলে "No its not a bitonic array" প্রিন্ট করুন।
বিটোনিক অ্যারে হলো যা প্রথমে স্ট্রিক্টলি ইনক্রিজিং অর্ডারে থাকে, তারপর স্ট্রিক্টলি ডিক্রিজিং অর্ডারে।
উদাহরণ: arr[] = {1, 2, 3, 4, 2, -1, -5} — ৪ পর্যন্ত বেড়েছে, তারপর কমেছে।
ইনপুট
arr[] = {1, 3, 5, 4, 2, 0}
আউটপুট
Yes its a bitonic array
ব্যাখ্যা — 1 < 3 < 5 > 4 > 2 > 0, তাই বিটোনিক।
ইনপুট
arr[] = {1, 2, 3, 4, 5, 0, -1, -2, 6, -4}
আউটপুট
No its not a bitonic array
পদ্ধতি
- অ্যারে ট্রভার্স করুন, যতক্ষণ arr[i] > arr[i-1] ততক্ষণ আগে বढুন।
- যখন arr[i] <= arr[i-1] হয়, লুপ ব্রেক করুন।
- তারপর বাকি অংশে arr[j] < arr[j-1] কিনা চেক করুন।
- যদি শেষ পর্যন্ত পৌঁছান এবং শর্ত পূরণ হয়, তবে বিটোনিক।
এলগরিদম
Start
Step 1 → int check(int arr[], int size)
int i, j
for i = 1 to size-1
if arr[i] > arr[i-1] continue
if arr[i] <= arr[i-1] break
if i == size-1 return 1
for j = i+1 to size-1
if arr[j] < arr[j-1] continue
if arr[j] >= arr[j-1] break
i = j
if i != size return 0
return 1
Step 2 → main(): অ্যারে ঘোষণা, check() কল, ফলাফল প্রিন্ট
Stop
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int check(int arr[], int size){
int i, j;
for (i = 1; i < size; i++){
if (arr[i] > arr[i - 1]) continue;
if (arr[i] <= arr[i - 1]) break;
}
if (i == size - 1) return 1;
for (j = i + 1; j < size; j++){
if (arr[j] < arr[j - 1]) continue;
if (arr[j] >= arr[j - 1]) break;
}
i = j;
if (i != size) return 0;
return 1;
}
int main(){
int arr[] = { -3, 9, 11, 20, 17, 5, 1 };
int size = sizeof(arr) / sizeof(arr[0]);
(check(arr, size) == 1) ? cout << "Yes its a bitonic array" : cout << "no its not a bitonic array";
return 0;
}
আউটপুট
Yes its a bitonic array
