Độ dài mảng con lớn nhất chỉ chứa số xấu trong C++

Đề bài

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

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

Ví dụ các số đầu tiên: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,...

Ví dụ

Nếu mảng đầu vào: {1, 2, 7, 9, 120, 810, 374} thì kết quả = 3 vì mảng con dài nhất là {9, 120, 810}

Thuật toán

1. Tạo unordered_set, chèn tất cả số xấu < 1000 vào set
2. Duyệt mảng với 2 biến: current_max và max_so_far
3. Kiểm tra từng phần tử có trong set không
4. Nếu là số xấu: tăng current_max, so sánh với max_so_far
5. Nếu không phải số xấu: reset current_max = 0

Chương trình C++

#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++;
            next_multiple_of_2 = ugly[i2] * 2;
        }
        if (next_ugly_no == next_multiple_of_3) {
            i3++;
            next_multiple_of_3 = ugly[i3] * 3;
        }
        if (next_ugly_no == next_multiple_of_5) {
            i5++;
            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;
}

Kết quả

Maximum sub-array size of consecutive ugly numbers = 3