Độ dài tối đa của một mảng con với các số xấu trong C ++

Tuyên bố vấn đề

Cho một mảng arr [] gồm N phần tử (0 ≤ arr [i] ≤ 1000). Nhiệm vụ là tìm độ dài tối đa của mảng con chỉ chứa các số xấu.

Số xấu là số có thừa số nguyên tố duy nhất là 2, 3 hoặc 5.

Ví dụ dưới đây là số ít từ các chuỗi:1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,…

Ví dụ

Nếu mảng đầu vào là {1, 2, 7, 9, 120, 810, 374} thì câu trả lời là 3 là -

Dãy con dài nhất có thể có của số xấu nhất {9, 120, 810}

Thuật toán

• Lấy một tập hợp không có thứ tự và chèn tất cả các số xấu hơn nhỏ hơn 1000 vào tập hợp
• Duyệt qua mảng với hai biến có tên là current_max và max_so_far.
• Kiểm tra từng phần tử nếu nó có trong tập hợp
• Nếu tìm thấy một số xấu, hãy tăng current_max và so sánh với max_so_far
• Nếu current_max> max_so_far thì max_so_far =current_max.
• Mỗi khi tìm thấy phần tử không xấu, hãy đặt lại current_max =0.

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Maximum sub-array size of consecutive ugly numbers = 3