คำอธิบายปัญหา
กำหนดอาร์เรย์ arr[] ของ N องค์ประกอบ (0 ≤ arr[i] ≤ 1000) งานคือการหาความยาวสูงสุดของซับอาร์เรย์ที่มีเฉพาะ Ugly Numbers
Ugly Numbers คือจำนวนที่ตัวประกอบเฉพาะ (prime factors) มีแค่ 2, 3 หรือ 5 เท่านั้น
ตัวอย่างเลข Ugly Numbers แรกๆ: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,...
ตัวอย่าง
ถ้าอาร์เรย์นำเข้าคือ {1, 2, 7, 9, 120, 810, 374} คำตอบคือ 3 ดังนี้:
ซับอาร์เรย์ที่ยาวที่สุดของ Ugly Numbers คือ {9, 120, 810}
อัลกอริทึม
- สร้าง unordered_set และใส่ Ugly Numbers ทั้งหมดที่น้อยกว่า 1000 ลงไปในเซต
- เดินทางผ่านอาร์เรย์ด้วยตัวแปรสองตัวคือ current_max และ max_so_far
- ตรวจสอบแต่ละองค์ประกอบว่าอยู่ในเซตหรือไม่
- ถ้าพบ Ugly Number ให้เพิ่ม current_max และเปรียบเทียบกับ max_so_far
- ถ้า current_max > max_so_far แล้ว max_so_far = current_max
- ทุกครั้งที่พบองค์ประกอบที่ไม่ใช่ Ugly ให้รีเซ็ต 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
