No Brute Force | Highly Optimized | Enough for n=1e5
Approach\nsuppose n = 20\nAll the prime factors of 30 = {2,3,5}\nand all the divisors of 20 = {1,2,3,6,5,10,15,30}\nwhich can be genrated by the combination fro
# Approach\nsuppose n = 20\nAll the prime factors of 30 = {2,3,5}\nand all the divisors of 20 = {1,2,3,6,5,10,15,30}\nwhich can be genrated by the combination from the prime numbers.\n# Code\n```\nclass Solution {\nprivate:\n    vector<int> allDivisor(int n){\n        // calculate all prime factors of n\n        map<int,int> primes;\n        for(long long i=2; i<=sqrt(n); i++) {\n            while(n%i == 0) {\n                primes[i]++;\n                n/=i;\n            }\n        }\n        if (n > 1) primes[n]++;\n\n        // make all divisors by primes\n        vector<int> divisors = {1};\n        for(auto&p: primes) {\n            int sz = divisors.size();\n            int cur = 1;\n            for (int i=0; i <p.second; i++) {\n                cur *= p.first;\n                for (int j = 0; j < sz; j++) {\n                    divisors.push_back(divisors[j] * cur);\n                }\n            }\n        }\n        return divisors;\n    }\npublic:\n    int maxDivScore(vector<int>& nums, vector<int>& divisors) {\n        map<int,int> freq; // used to store the frequency of each number which is the factor if nums[i]\n        set<int> st(begin(divisors),end(divisors)); // It\'s for like storing the frequency of elements which is only present in divisors array. (It\'s for space optimisation)\n\n        // storing the divisors of all the elements of nums[i]\n        for(int&num: nums){\n            auto factors = allDivisor(num);\n            for(int&factor: factors)\n                if(st.count(factor)) freq[factor]++;\n        }\n\n        // simply checking the freq of each divisors[i] in freq map\n        int maxfreq = -1,ans = -1,mn = 1e9;\n        for(int&e: divisors){\n            if(freq.count(e)){\n                int val = freq[e];\n                if(maxfreq < val){\n                    maxfreq = val;\n                    ans = e;\n                }else if(maxfreq == val){\n                    ans = min(ans,e);\n                }\n            }\n            mn = min(mn,e);\n        }\n        return ans == -1 ? mn : ans;\n    }\n};\n```
['Array', 'Hash Table', 'Math', 'Ordered Set', 'C++']