Tìm số nguyên chia số phần tử tối đa của mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n số nguyên.

Nhiệm vụ của chúng ta là tìm số nguyên chia tối đa số phần tử của mảng.

Mô tả sự cố: Chúng ta cần tìm một số p có thể chia số phần tử tối đa của mảng. Trong trường hợp có nhiều hơn một phần tử như vậy, chúng tôi sẽ trả về phần tử nhỏ hơn.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: arr [] ={4, 5, 6, 7, 8}

Đầu ra: 2

Giải thích:

Phần tử 2 chia {4, 6, 8}.

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là lặp qua mảng và sau đó với mỗi phần tử của mảng, hãy chia mỗi phần tử trong mảng với các phần tử từ 1 đến k. Và trả về phần tử chia số phần tử tối đa của mảng.

Một cách tiếp cận khác để giải quyết vấn đề bằng cách sử dụng thực tế là tất cả các phần tử của mảng đều được chia cho các thừa số nguyên tố.

Chúng tôi sẽ lưu trữ tần số chia cho từng số nguyên tố và sau đó trả về thừa số với tần suất lớn nhất. Chúng tôi lưu trữ các số nguyên tố và tần số của chúng trong một hàm băm.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <bits/stdc++.h>
using namespace std;

#define MAXN 100001
int primes[MAXN];

void findPrimeSieve()
{
   primes[1] = 1;
   for (int i = 2; i < MAXN; i++)
      primes[i] = i;
   for (int i = 4; i < MAXN; i += 2)
      primes[i] = 2;

   for (int i = 3; i * i < MAXN; i++) {
      if (primes[i] == i) {
         for (int j = i * i; j < MAXN; j += i)
            if (primes[j] == j)
               primes[j] = i;
      }
   }
}

vector<int> findFactors(int num)
{
   vector<int> factors;
   while (num != 1) {
      int temp = primes[num];
      factors.push_back(temp);
      while (num % temp == 0)
         num = num / temp;
   }
   return factors;
}

int findmaxDivElement(int arr[], int n) {

   findPrimeSieve();
   map<int, int> factorFreq;
   for (int i = 0; i < n; ++i) {

      vector<int> p = findFactors(arr[i]);
      for (int i = 0; i < p.size(); i++)
         factorFreq[p[i]]++;
   }

   int cnt = 0, ans = 1e+7;
   for (auto itr : factorFreq) {
      if (itr.second >= cnt) {
         cnt = itr.second;
         ans > itr.first ? ans = itr.first : ans = ans;
      }
   }

   return ans;
}

int main() {

   int arr[] = { 4, 5, 6, 7, 8 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The number that divides the maximum elements of the array is "<<findmaxDivElement(arr, n);
   return 0;
}

Đầu ra

The number that divides the maximum elements of the array is 2