Binary Search approach with Intuition
We can get highest frequency in 2 ways.\n\n1) By converting some numbers into a number which exists in the array.\n2) By converting some numbers into a number w
We can get highest frequency in 2 ways.\n\n1) By converting some numbers into a number which exists in the array.\n2) By converting some numbers into a number which doesn\'t exist.\n\nFirst calculate frequencies of all elements and then calculate prefix sum of their frequencies.\n\nNow for the first part we take each number as the center (i.e all the numbers will be converted to this number.) then conduct a binary search to look for boundary indexes in the array which comply with the range. Then use prefix sum to calculate the number of operations. If they are more than Maxoperations then compare maxi with MaxOperations.\n\n\nThe intution behind the second part is that there might exist a better number which doesn\'t exist in the array and a bigger range can be converted into that number. For eg. 1, 4, 10, 12. and k = 4, maxop = 3;\nHere 4, 10 and 14 can be converted into 8 which doesn\'t exist in the array.\n\nWhat we can do is for each nums[i] we try to find a range which starts with nums[i] goes upto nums[i] + 2k and the middle number is obviously nums[i] + k.\n\nFor this middle number i.e nums[i] + k we find upper and lower bounds (l1, r1, l2, r2). After that we just have to follow the same procedure what we did for the 1st.\n\nPrefix sum will let you calculate the frequencies of the range in O(1) time.\n\n\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n\n    int binleft(vector <int> &nums, int i, int k) {\n\n        int low = 0, high = nums.size() - 1, ans = -1;\n            \n            \n        while (low <= high) {\n\n            int mid = low + (high - low) / 2;\n\n\n            if (i - nums[mid] <= k) {\n                \n                if(i - nums[mid] >= 0) ans = mid;\n                \n                high = mid - 1;\n\n            }\n\n\n            else {\n                \n                low = mid + 1;\n\n\n            }\n        }\n\n        return ans;\n\n    }\n    \n    \n    \n    int binright(vector <int> &nums, int i, int k) {\n\n        int low = 0, high = nums.size() - 1, ans = -1;\n            \n            \n        while (low <= high) {\n\n            int mid = low + (high - low) / 2;\n\n\n            if (nums[mid] - i <= k) {\n        \n                if(nums[mid] - i >= 0) ans = mid;\n                \n                low = mid + 1;\n\n            }\n\n\n            else {\n                \n                high = mid - 1;\n\n\n            }\n        }\n\n        return ans;\n    }\n\n\n    int lnear(vector <int> &nums, int i) {\n\n        int low = 0, high = nums.size() - 1, ans = -1;\n            \n            \n        while (low <= high) {\n\n            int mid = low + (high - low) / 2;\n\n\n            if (nums[mid] < i) {\n                \n                ans = mid;\n\n                \n                low = mid + 1;\n\n            }\n\n\n            else {\n                \n                high = mid - 1;\n\n\n            }\n        }\n\n        return ans;\n    }\n\n    int rnear(vector <int> &nums, int i) {\n\n        int low = 0, high = nums.size() - 1, ans = -1;\n\n\n        while (low <= high) {\n\n            int mid = low + (high - low) / 2;\n\n\n            if (nums[mid] > i) {\n                \n                ans = mid;\n\n\n                high = mid - 1;\n\n            }\n\n\n            else {\n\n                low = mid + 1;\n\n\n            }\n\t    }\n\n\t    return ans;\n    }   \n\n\n    int maxFrequency(vector<int>& nums, int k, int x) {\n\n        unordered_map <int, int> m;\n\n        if(nums.size() == 1) return 1;\n        \n        vector <int> v;\n\n        int maxi = INT_MIN;\n        \n        for(auto i: nums) {\n            \n            if(m[i] == 0) v.push_back(i);\n            \n            m[i]++;\n        }\n        \n        sort(v.begin(), v.end());\n        \n        vector <int> pre(v.size(), 0);\n        \n        pre[0] = m[v[0]];\n        \n        for(int i = 1; i < v.size(); i++) {\n            \n            pre[i] = pre[i - 1] + m[v[i]];\n        }\n\n        for(int i = 0; i < v.size(); i++) {\n\n            int temp = v[i] + k;\n            int temp2 = v[i] + 2*k;\n\n            if(m[temp2] != 0) temp2++;\n\n            int l1 = i;\n            int l2 = rnear(v, temp);\n            int r1 = lnear(v, temp);\n            int r2 = lnear(v, temp2);\n\n            // cout << "i: " << i << " " << l1 << " " << r1 << " " << l2 << " " << r2 << endl;\n\n            if(r1 >= l1 and l2 != -1 and r2 >= l2) {\n\n                int cnt = pre[r2] - pre[l2] + m[v[l2]] - m[temp];\n\n                cnt += pre[r1] - pre[l1] + m[v[l1]];\n\n                if(cnt > x) cnt = x;\n\n                // cout << cnt << endl;\n\n                maxi = max(maxi, m[temp] + cnt);\n            }\n\n            else if(r1 >= l1){\n\n\n                int cnt = pre[r1] - pre[l1] + m[v[l1]] - m[temp];\n\n                if(cnt > x) cnt = x;\n\n                maxi = max(maxi, m[temp] + cnt);\n\n\n            }\n\n            int j = v[i];\n\n\n            int left = binleft(v, j, k);\n            \n            int right = binright(v, j, k);\n\n            if(left != -1 and right != -1) {\n                \n                int cnt = pre[right] - pre[left] + m[v[left]] - m[j];\n                \n                if(cnt > x) cnt = x;\n                // cout << j << " " << m[j] + cnt << " " << left << " " << right << endl;\n                \n                maxi = max(maxi, m[j] + cnt);\n                \n                \n            }\n            \n            else if(right != -1) {\n                \n                int ind = lnear(v, j);\n                \n                int y = 0;\n                \n                if(ind != -1) y = pre[ind];\n                \n                \n                \n                \n                int cnt = pre[right] - y;\n                \n                if(cnt > x) cnt = x;\n                \n                // cout << j << " " << cnt << " " << y << endl;\n                \n                \n                maxi = max(maxi, cnt); \n            }\n            \n            else if(left != -1) {\n                \n                int ind = lnear(v, j);\n                \n                int y = 0;\n                \n                if(ind != -1) y = pre[ind];\n                \n                \n                \n                \n                int cnt = y - pre[left];\n                \n                if(cnt > x) cnt = x;\n                \n                // cout << j << " " << cnt << " " << y << endl;\n                \n                \n                maxi = max(maxi, cnt); \n                \n                \n            }\n\n\n\n\n\n        }\n\n        return maxi;\n        \n    }\n};\n```
['Binary Search', 'Sorting', 'Prefix Sum', 'C++']