#gujju_ben_ni_gamzzat
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nsauthi pehli vat to ke 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nsauthi pehli vat to ke brute force method na andar => O(n*n) ..first n is for iterating through all the values of n and then calculating ke ketlo cost lage 6e for each n for the other n number ...and is it lesser than or equal to k \n\nfirst n ne to hu nano nathi kari sakto karan ke I need to try all the possible solutions ke kaya n of nums ni value mate result  apda ne max_Frequency_score api sake 6e...then rahi vat bija n ni aena ma to je number of operations 6e aene to hu minimize kari saku 6u => ae to agad joisu ke ae kevi ritna thai 6e.\n\nmara binary search on input to nahi lagavi sakai as I need to check for all the values in nums.=> then would try for the binary search in output....  to reduce the time complexity. \n\n`  int n=nums.length;`\n\n have ae vastu haji ek samajh vani 6e ke nums na koi pan ek aeva element ni frequency ne maximize karvani 6e then ... ae to dhyan hase ke je pan element aena close hase ae loko ne hu change karvano try karu then hu vadhare fayda ma rahis...atle ke ae element na subarray na j element ne convert karvano rehse within k operations and ...and ae subarray ni je pan length hase that would be equal to max_score of the array. => atla mate to hu array ne sort kari dais je thi ke mane subarray find out karvama asani reh. \n\n    Arrays.sort(nums);\n\n    long prefix_sum[]=new long[n+1];\n\n    prefix_sum[1]= nums[0];\n    for(int i=2;i<=n;i++){\n        prefix_sum[i] = prefix_sum[i-1] + nums[i-1];\n    }\n\ntame j vichar karo ke min_score su thai sake 6e?? 1 ..karan ke as we have already proved ke apde target_element ne from the array mathi j laisu then aeno atleast ek vakht to occurence pakko 6e j. */\n/*max_score su thai sake 6e?? jyare badha element apda target element na equal thai jai. \n\n    int min_score=1,max_score=n;\n    System.out.println("min_score: "+min_score+" max_score: "+max_score);\n\nas previosly discussed ke mare output na upar binary search lagadvanu 6e... ahiya output su ke  score value 6e.... to aena upar binary search ne lagado and find out karo ke value possible 6e ke nathi. \n\n    int result_score=1;\n\n    while(min_score<= max_score){\n            int mid_score= (min_score) + (max_score-min_score)/2;\n            // System.out.println("mid_score: "+mid_score);\n            /*agar jo aa mid_score apda array ma possible 6e then apde to vadhare greedy thai ne check karisu ke ana agad no score achievable 6e ke nathi?? => but for the time being apda result ma aa vadi value ne store kari daiye 6e. */\n            if(is_possible(nums,k,n,mid_score, prefix_sum)){\n                result_score=mid_score;\n                min_score=mid_score+1;\n            }else {\n    /*agar jo given frequency/score mate answer possible nathi => then aena karti ochi frequency mate find out karvani koshish karo. */\n                max_score=mid_score-1;\n            }\n        }\n\n         return result_score; \n\n---\n**is possible vadu function**\n\nmid_score is the score to be achieved for any element in the array.\n  \nthe task is to find out ke this target_score is acheivable in the array or not. \n\nnow I\'ll iterate through all the windows of the length=target_score to check whether there is any window ke jena andar aa score possible 6e ke nathi.=> then I\'ll start with  i=0 and j=target_score-1 at first. \n\nhave ae question arise thai 6e ke target_score/target_frequency to khabar padi gai ke su lavani 6e => but kaya element mate ??? => median of the subarray...earlier as we have proved ke sorted array na andar elements ne median na upar equalize karisu then ae kam apdu minimum number of operations na andar thase. \n\nmedian_idx to find out thai gayu but have ae target_element na equal karva mate bija badha elements na upar iterate karvu padse ke ketla number of operation required 6e => to-to farithi O(n) add thai jase...but rather hu pehla thi j aemnoo prefix_sum ne calculate karine besu and then aena prefix_sum mathi num_elemts*target_elemt ne minus kari dais to mane easily number of operations madi jase.  => to hu aene ek j vakht mara main function na andar calculate karine ahiya darek vakhte pass kari dau to ketlo badho time bachse. \n\nnow as I have the prefix_sum...calculate how many elements are towards the left and their expected sum and minus it from their actual sum and get the number of operations required to convert the left subarray part to the given target_val so to get the given target_score. \n\n\n        int start=0, end= target_score-1;\n        // System.out.println("start: "+start+" end: "+end);\n        while(end<n){\n                int median_idx= (start+end)/2;\n                long target_val= nums[median_idx];\n                // System.out.println("median_idx: "+median_idx+ " target_val: "+target_val );\n\n                int elements_left= median_idx - start;\n                long expected_left_sum = (target_val * elements_left);\n                long actual_left_sum = actual_prefix_sum[median_idx] - actual_prefix_sum[start];\n            // System.out.println("elements_left: "+elements_left+ " expected_left_sum:  "+expected_left_sum+" actual_left_sum: "+actual_left_sum);\n\n                int elements_right = end- median_idx ;\n                long expected_right_sum = (target_val * elements_right);\n                long actual_right_sum = actual_prefix_sum[end+1] - actual_prefix_sum[median_idx+1];\n            // System.out.println("elements_right: "+elements_right+ " expected_right_sum:  "+expected_right_sum+" actual_right_sum: "+actual_right_sum);\n            \n                long curr_operations = Math.abs(actual_left_sum-expected_left_sum) + Math.abs(expected_right_sum-actual_right_sum);\n                // System.out.println("curr_operations: "+curr_operations);\n            \n                if(curr_operations<=k){\n                    /*if we can reach the target_value with the target_score in the given subarray with the curr_operations where the curr_operations would be less than the max allowed operations(k) then return true. */\n                    return true;\n                }\n            // System.out.println("--------------");\n                /*if it is not found yet then => search in the another window...slide the window. */\n                start++;end++;\n        }\n\n        return false;\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nSort the nums : O(n* log(n))\n\nget the score: O(log(n))\n\ncheck if possible : O(n) => when the window size=1 \n\noverall time complexity of the last two functions is : O(n* log(n))\n=====\nOveral time complexity of the function is : O(n * log(n))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nPrefix_sum: O(n)\n\n# Code\n```\nclass Solution {\n    public static void print(int arr[]){\n        for(int i=0;i<arr.length;i++){\n            System.out.print(arr[i]+" ");\n        }\n        System.out.println();\n    }\n    public static void print_long(long arr[]){\n        for(int i=0;i<arr.length;i++){\n            System.out.print(arr[i]+" ");\n        }\n        System.out.println();\n    }\n    public static boolean is_possible(int nums[],long k,int n,int target_score,long actual_prefix_sum[]){\n        /*mid_score is the score to be achieved for any element in the array  */\n        /*the task is to find out ke this target_score is acheivable in the array or not. */\n\n        /*now I\'ll iterate through all the windows of the length=target_score to check whether there is any window ke jena andar aa score possible 6e ke nathi.=> then I\'ll start with  i=0 and j=target_score-1 at first. */\n\n        /*have ae question arise thai 6e ke target_score/target_frequency to khabar padi gai ke su lavani 6e => but kaya element mate ??? => median of the subarray...earlier as we have proved ke sorted array na andar elements ne median na upar equalize karisu then ae kam apdu minimum number of operations na andar thase. */\n\n        /*median_idx to find out thai gayu but have ae target_element na equal karva mate bija badha elements na upar iterate karvu padse ke ketla number of operation required 6e => to-to farithi O(n) add thai jase...but rather hu pehla thi j aemnoo prefix_sum ne calculate karine besu and then aena prefix_sum mathi num_elemts*target_elemt ne minus kari dais to mane easily number of operations madi jase.  => to hu aene ek j vakht mara main function na andar calculate karine ahiya darek vakhte pass kari dau to ketlo badho time bachse. */\n\n/*now as I have the prefix_sum...calculate how many elements are towards the left and their expected sum and minus it from their actual sum and get the number of operations required to convert the left subarray part to the given target_val so to get the given target_score. */\n\n\n        int start=0, end= target_score-1;\n        // System.out.println("start: "+start+" end: "+end);\n        while(end<n){\n                int median_idx= (start+end)/2;\n                long target_val= nums[median_idx];\n                // System.out.println("median_idx: "+median_idx+ " target_val: "+target_val );\n\n                int elements_left= median_idx - start;\n                long expected_left_sum = (target_val * elements_left);\n                long actual_left_sum = actual_prefix_sum[median_idx] - actual_prefix_sum[start];\n            // System.out.println("elements_left: "+elements_left+ " expected_left_sum:  "+expected_left_sum+" actual_left_sum: "+actual_left_sum);\n\n                int elements_right = end- median_idx ;\n                long expected_right_sum = (target_val * elements_right);\n                long actual_right_sum = actual_prefix_sum[end+1] - actual_prefix_sum[median_idx+1];\n            // System.out.println("elements_right: "+elements_right+ " expected_right_sum:  "+expected_right_sum+" actual_right_sum: "+actual_right_sum);\n            \n                long curr_operations = Math.abs(actual_left_sum-expected_left_sum) + Math.abs(expected_right_sum-actual_right_sum);\n                // System.out.println("curr_operations: "+curr_operations);\n            \n                if(curr_operations<=k){\n                    /*if we can reach the target_value with the target_score in the given subarray with the curr_operations where the curr_operations would be less than the max allowed operations(k) then return true. */\n                    return true;\n                }\n            // System.out.println("--------------");\n                /*if it is not found yet then => search in the another window...slide the window. */\n                start++;end++;\n        }\n\n        return false;\n    }\n    public int maxFrequencyScore(int[] nums, long k) {\n     /*sauthi pehli vat to ke brute force method na andar => O(n*n) ..first n is for iterating through all the values of n and then calculating ke ketlo cost lage 6e for each n for the other n number ...and is it lesser than or equal to k */\n     /*first n ne to hu nano nathi kari sakto karan ke I need to try all the possible solutions ke kaya n of nums ni value mate result  apda ne max_Frequency_score api sake 6e...then rahi vat bija n ni aena ma to je number of operations 6e aene to hu minimize kari saku 6u => ae to agad joisu ke ae kevi ritna thai 6e. */ \n     /*mara binary search on input to nahi lagavi sakai as I need to check for all the values in nums.=> then would try for the binary search in output....  to reduce the time complexity. */ \n     int n=nums.length;\n/* have ae vastu haji ek samajh vani 6e ke nums na koi pan ek aeva element ni frequency ne maximize karvani 6e then ... ae to dhyan hase ke je pan element aena close hase ae loko ne hu change karvano try karu then hu vadhare fayda ma rahis...atle ke ae element na subarray na j element ne convert karvano rehse within k operations and ...and ae subarray ni je pan length hase that would be equal to max_score of the array. => atla mate to hu array ne sort kari dais je thi ke mane subarray find out karvama asani reh. */\n\n    Arrays.sort(nums);\n    // print(nums);\n\n    long prefix_sum[]=new long[n+1];\n\n    prefix_sum[1]= nums[0];\n    for(int i=2;i<=n;i++){\n        prefix_sum[i] = prefix_sum[i-1] + nums[i-1];\n    }\n    // print_long(prefix_sum);\n\n/*tame j vichar karo ke min_score su thai sake 6e?? 1 ..karan ke as we have already proved ke apde target_element ne from the array mathi j laisu then aeno atleast ek vakht to occurence pakko 6e j. */\n/*max_score su thai sake 6e?? jyare badha element apda target element na equal thai jai. */\n    int min_score=1,max_score=n;\n    // System.out.println("min_score: "+min_score+" max_score: "+max_score);\n    /*as previosly discussed ke mare output na upar binary search lagadvanu 6e... ahiya output su ke  score value 6e.... to aena upar binary search ne lagado and find out karo ke value possible 6e ke nathi. */\n    int result_score=1;\n\n    while(min_score<= max_score){\n        int mid_score= (min_score) + (max_score-min_score)/2;\n        // System.out.println("mid_score: "+mid_score);\n        /*agar jo aa mid_score apda array ma possible 6e then apde to vadhare greedy thai ne check karisu ke ana agad no score achievable 6e ke nathi?? => but for the time being apda result ma aa vadi value ne store kari daiye 6e. */\n        if(is_possible(nums,k,n,mid_score, prefix_sum)){\n            result_score=mid_score;\n            min_score=mid_score+1;\n        }else {\n/*agar jo given frequency/score mate answer possible nathi => then aena karti ochi frequency mate find out karvani koshish karo. */\n            max_score=mid_score-1;\n        }\n    }\n     return result_score; \n    }\n}\n```\n
['Java']