C++에서 못생긴 숫자가 있는 하위 배열의 최대 길이

문제 설명

N개의 요소(0 ≤ arr[i] ≤ 1000)의 배열 arr[]이 제공됩니다. 작업은 못생긴 숫자만 포함하는 하위 배열의 최대 길이를 찾는 것입니다.

못생긴 숫자는 소인수가 2, 3 또는 5뿐인 숫자입니다.

예를 들어 아래는 시리즈의 몇 가지 숫자입니다:1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,…

예시

입력 배열이 {1, 2, 7, 9, 120, 810, 374}이면 답은 −

못생긴 숫자 sis {9, 120, 810}의 가능한 가장 긴 하위 배열

알고리즘

• unordered_set을 가져와서 집합에 1000보다 작은 모든 못생긴 숫자를 삽입합니다.
• 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