সমস্যা বিবরণ
N উপাদানের একটি অ্যারে arr[] দেওয়া আছে (0 ≤ arr[i] ≤ 1000)। কাজ হলো শুধু অসুন্দর সংখ্যা (ugly numbers) ধারণকারী সাব-অ্যারের সর্বোচ্চ দৈর্ঘ্য বের করা।
অসুন্দর সংখ্যা (Ugly numbers) হলো এমন সংখ্যা যাদের প্রাইম ফ্যাক্টর শুধু ২, ৩ বা ৫।
উদাহরণস্বরূপ নিচে সিরিজের কিছু সংখ্যা দেওয়া হলো: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,…
উদাহরণ
ইনপুট অ্যারে যদি {1, 2, 7, 9, 120, 810, 374} হয়, তবে উত্তর হবে ৩ কারণ −
অসুন্দর সংখ্যার সবচেয়ে লম্বা সাব-অ্যারে হলো {9, 120, 810}
অ্যালগরিদম
- একটি unordered_set নিন, এবং ১০০০-এর চেয়ে ছোট সকল অসুন্দর সংখ্যা সেটে ইনসার্ট করুন
- দুটি ভেরিয়েবল current_max এবং max_so_far নিয়ে অ্যারে ট্রাভার্স করুন।
- প্রতিটি উপাদানের জন্য যাচাই করুন সেটে আছে কিনা
- যদি অসুন্দর সংখ্যা পাওয়া যায়, তবে current_max বাড়ান এবং max_so_far-এর সাথে তুলনা করুন
- যদি current_max > max_so_far হয় তবে max_so_far = current_max করুন।
- প্রতিবার নন-অসুন্দর উপাদান পাওয়া গেলে current_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
