Find Divisors of All Elements | Time Complexity Explained | C++
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(N + N * sqrt(maxElement) + maxElement + maxElement * sqrt(maxElement) + maxElement + Q * log(maxElement))\n\n- Space complexity: O(maxElement)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    void findDivisorsFreq(vector<int>& nums, vector<int>& div) {\n        int n = nums.size();\n        for(int i=0; i<n; i++) {\n            for(int j=1; j*j<=nums[i]; j++) {\n                if(nums[i] % j == 0) {\n                    div[j]++;\n                    if(nums[i] / j != j) div[nums[i] / j]++;\n                }\n            }\n        }\n    }\n\n    void findGCDCount(vector<int>& div) {\n        int n = div.size();\n        for(int i=0; i<n; i++) div[i] = (div[i] * 1LL * (div[i] - 1)) / 2; // nC2 find\n    }\n\n    void decreaseCount(vector<int>& div) {\n        int n = div.size();\n        for(int i=n-1; i>=1; i--) {\n            for(int j=1; j*j<=i; j++) {\n                if(j == i) continue;\n                if(i % j == 0) {\n                    div[j] -= div[i];\n                    if(i / j != j && (i / j) != i) div[i / j] -= div[i];\n                }\n            }\n        }\n    }\n\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) {\n        int maxElement = *max_element(nums.begin(), nums.end()); // N time\n        vector<int> div (maxElement + 1, 0); // find array of highest gcd possible\n\n        findDivisorsFreq(nums, div); // each poss divisor -> N * sqrt(maxElement) time\n        findGCDCount(div); // each possible gcd count -> maxElement time\n        decreaseCount(div); // subtract higher gcd no count from lower gcd no count -> maxElement * sqrt(maxElement) time\n\n        // prfix sum\n        int n = div.size();\n        for(int i=1; i<n; i++) div[i] += div[i - 1]; // maxElement time\n\n        // binary of search over gcd\'s:\n        vector<int> ans;\n        for(auto i: queries) { // q * log(maxElement) time\n            int elementNo = i + 1;\n            int index = lower_bound(div.begin(), div.end(), elementNo) - div.begin();\n            ans.push_back(index);\n        }\n        return ans;\n    }\n};\n```
['Array', 'Math', 'Binary Search', 'Combinatorics', 'Counting', 'Prefix Sum', 'C++']