Binary Search on Answer | CodestorywithMIK
YouTube Video Coming soon today - https://www.youtube.com/watch?v=Iaz-8ZQYUvs\n\n\n/************************************ C++ ***********************************
YouTube Video Coming soon today - https://www.youtube.com/watch?v=Iaz-8ZQYUvs\n\n```\n/************************************ C++ ****************************************/\nclass Solution {\n    typedef long long int ll;\n    bool IsPossible (int len, const vector<int>& nums, const vector<ll>& prefix, const ll K, int n) {\n        if(len == 0)\n            return false;\n        \n        int i = 0;\n        int j = len-1;\n        \n        while(j < n) {\n            ll target_idx = (i+j) / 2;\n            ll target     = nums[target_idx];\n            \n            \n            ll operations_left  = 0;\n            ll operations_right = 0;\n            \n            if(target_idx == 0) {\n                operations_left = 0;\n            } else {\n                operations_left = abs(((target_idx - i) * target) - (prefix[target_idx-1] - (i > 0 ? prefix[i-1] : 0)));\n            }\n            \n            operations_right    = abs(((j - target_idx) * target) - (prefix[j] - prefix[target_idx]));\n          \n            if(operations_right + operations_left <= K) {\n                return true;\n            }\n            \n            i++;\n            j++;\n            \n        }\n        \n        return false;\n    }\n    \npublic:\n    int maxFrequencyScore(vector<int>& nums, long long k) {\n        int n = nums.size();\n        sort (nums.begin(), nums.end());\n        \n        vector<ll> prefix(n, 0);\n        prefix[0] = nums[0];\n        for (int i = 1; i < n; i++) \n            prefix[i] = prefix[i-1] + nums[i];\n        \n        int min_score     = 1;\n        int max_score     = n;\n        int result_score  = 1;\n        \n        while (min_score <= max_score) {\n            int mid = (min_score + max_score) / 2;\n            \n            if (IsPossible(mid, nums, prefix, k, n)) {\n                result_score = mid;\n                min_score = mid + 1;\n            } else {\n                max_score = mid - 1;\n            }\n        }\n        \n        return result_score;\n    }\n};\n\n\n/************************************ JAVA ****************************************/\nclass Solution {\n    private boolean isPossible(int len, int[] nums, long[] prefix, long k, int n) {\n        if (len == 0)\n            return false;\n\n        int i = 0;\n        int j = len - 1;\n\n        while (j < n) {\n            long targetIdx = (i + j) / 2;\n            long target = nums[(int) targetIdx];\n\n            long operationsLeft;\n            long operationsRight;\n\n            if (targetIdx == 0) {\n                operationsLeft = 0;\n            } else {\n                operationsLeft = Math.abs(((targetIdx - i) * target)\n                        - (prefix[(int) targetIdx - 1] - (i > 0 ? prefix[i - 1] : 0)));\n            }\n\n            operationsRight = Math.abs(((j - targetIdx) * target) - (prefix[j] - prefix[(int) targetIdx]));\n\n            if (operationsRight + operationsLeft <= k) {\n                return true;\n            }\n\n            i++;\n            j++;\n        }\n\n        return false;\n    }\n\n    public int maxFrequencyScore(int[] nums, long k) {\n        int n = nums.length;\n        Arrays.sort(nums);\n\n        long[] prefix = new long[n];\n        prefix[0] = nums[0];\n        for (int i = 1; i < n; i++)\n            prefix[i] = prefix[i - 1] + nums[i];\n\n        int minScore = 1;\n        int maxScore = n;\n        int resultScore = 1;\n\n        while (minScore <= maxScore) {\n            int mid = (minScore + maxScore) / 2;\n\n            if (isPossible(mid, nums, prefix, k, n)) {\n                resultScore = mid;\n                minScore = mid + 1;\n            } else {\n                maxScore = mid - 1;\n            }\n        }\n\n        return resultScore;\n    }\n}\n```\n
['C', 'Java']