Maximize length of subarray having equal elements by adding at most K | Java program for above approach ; Function to find the maximum number of indices having equal elements after adding at most k numbers ; Sort the array in ascending order ; Make prefix sum array ; Initialize variables ; Update mid ; Check if any subarray can be obtained of length mid having equal elements ; Decrease max to mid ; Function to check if a subarray of length len consisting of equal elements can be obtained or not ; Sliding window ; Last element of the sliding window will be having the max size in the current window ; The current number of element in all indices of the current sliding window ; If the current number of the window , added to k exceeds totalNumbers ; Driver Code ; Function call
import java . util . * ; class GFG { public static int maxEqualIdx ( int [ ] arr , int k ) { Arrays . sort ( arr ) ; int [ ] prefixSum = new int [ arr . length + 1 ] ; prefixSum [ 1 ] = arr [ 0 ] ; for ( int i = 1 ; i < prefixSum . length - 1 ; ++ i ) { prefixSum [ i + 1 ] = prefixSum [ i ] + arr [ i ] ; } int max = arr . length ; int min = 1 ; int ans = 1 ; while ( min <= max ) { int mid = ( max + min ) / 2 ; if ( check ( prefixSum , mid , k , arr ) ) { ans = mid ; min = mid + 1 ; } else { max = mid - 1 ; } } return ans ; } public static boolean check ( int [ ] pSum , int len , int k , int [ ] a ) { int i = 0 ; int j = len ; while ( j <= a . length ) { int maxSize = a [ j - 1 ] ; int totalNumbers = maxSize * len ; int currNumbers = pSum [ j ] - pSum [ i ] ; if ( currNumbers + k >= totalNumbers ) { return true ; } else { i ++ ; j ++ ; } } return false ; } public static void main ( String [ ] args ) { int [ ] arr = { 1 , 1 , 1 } ; int k = 7 ; System . out . println ( maxEqualIdx ( arr , k ) ) ; } }