সমস্যা বিবৃতি
N উপাদানগুলির একটি অ্যারে arr[] দেওয়া হয়েছে (0 ≤ arr[i] ≤ 1000)। কাজটি হল উপ-অ্যারের সর্বাধিক দৈর্ঘ্য খুঁজে বের করা যাতে শুধুমাত্র কুৎসিত সংখ্যা থাকে।
কুৎসিত সংখ্যা হল এমন সংখ্যা যার একমাত্র মৌলিক গুণনীয়ক হল 2, 3 বা 5৷
উদাহরণের জন্য নিচে সিরিজ থেকে কয়েকটি সংখ্যা দেওয়া হল:1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,…
উদাহরণ
যদি ইনপুট অ্যারে হয় {1, 2, 7, 9, 120, 810, 374} তাহলে উত্তর হল 3 হিসাবে −
কুশ্রী সংখ্যা sis {9, 120, 810}
এর দীর্ঘতম সম্ভাব্য উপ-অ্যারেঅ্যালগরিদম
- একটি unordered_set নিন, এবং সেটে 1000-এর কম সব কুৎসিত সংখ্যা সন্নিবেশ করুন
- কারেন্ট_ম্যাক্স এবং ম্যাক্স_সো_ফার নামের দুটি ভেরিয়েবল দিয়ে অ্যারেটি অতিক্রম করুন।
- সেটে উপস্থিত আছে কিনা প্রতিটি উপাদানের জন্য পরীক্ষা করুন
- যদি একটি কুৎসিত সংখ্যা পাওয়া যায়, তাহলে বর্তমান_ম্যাক্স বৃদ্ধি করুন এবং এটিকে max_so_far এর সাথে তুলনা করুন
- যদি current_max> max_so_far হয় তাহলে max_so_far =current_max।
- যতবার একটি অ-কুশ্রী উপাদান পাওয়া যায়, বর্তমান_max =0 রিসেট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
unsigned getUglyNumbers(int n) {
int ugly[n];
int i2 = 0, i3 = 0, i5 = 0;
int next_multiple_of_2 = 2;
int next_multiple_of_3 = 3;
int next_multiple_of_5 = 5;
int next_ugly_no = 1;
ugly[0] = 1;
for (int i = 1; i < n; i++) {
next_ugly_no = min(next_multiple_of_2, min(next_multiple_of_3, next_multiple_of_5));
ugly[i] = next_ugly_no;
if (next_ugly_no == next_multiple_of_2) {
i2 = i2 + 1;
next_multiple_of_2 = ugly[i2] * 2;
}
if (next_ugly_no == next_multiple_of_3) {
i3 = i3 + 1;
next_multiple_of_3 = ugly[i3] * 3;
}
if (next_ugly_no == next_multiple_of_5) {
i5 = i5 + 1;
next_multiple_of_5 = ugly[i5] * 5;
}
}
return next_ugly_no;
}
int maxUglySubarray(int arr[], int n) {
unordered_set<int> s;
int i = 1;
while (1) {
int next_ugly_number = getUglyNumbers(i);
if (next_ugly_number > 1000)
break;
s.insert(next_ugly_number);
i++;
}
int current_max = 0, max_so_far = 0;
for (int i = 0; i < n; i++) {
if (s.find(arr[i]) == s.end())
current_max = 0;
else {
current_max++;
max_so_far = max(current_max,
max_so_far);
}
}
return max_so_far;
}
int main() {
int arr[] = {1, 2, 7, 9, 120, 810, 374};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sub-array size of consecutive ugly numbers = " << maxUglySubarray(arr, n) << endl;
return 0;
} আউটপুট
আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি নিম্নলিখিত আউটপুট −
তৈরি করেMaximum sub-array size of consecutive ugly numbers = 3
