Maximize length of subarray having equal elements by adding at most K | C ++ 14 program for above approach ; 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 ; 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 ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool check ( vector < int > pSum , int len , int k , vector < int > a ) { int i = 0 ; int j = len ; while ( j <= a . size ( ) ) { 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 ; } int maxEqualIdx ( vector < int > arr , int k ) { sort ( arr . begin ( ) , arr . end ( ) ) ; vector < int > prefixSum ( arr . size ( ) ) ; prefixSum [ 1 ] = arr [ 0 ] ; for ( int i = 1 ; i < prefixSum . size ( ) - 1 ; ++ i ) { prefixSum [ i + 1 ] = prefixSum [ i ] + arr [ i ] ; } int max = arr . size ( ) ; 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 ; } int main ( ) { vector < int > arr = { 1 , 1 , 1 } ; int k = 7 ; cout << ( maxEqualIdx ( arr , k ) ) ; }