Largest subset having with sum less than equal to sum of respective indices | Function to find the length of the longest subset ; Stores the sum of differences between elements and their respective index ; Stores the size of the subset ; Iterate over the array ; If an element which is smaller than or equal to its index is encountered ; Increase count and sum ; Store the difference with index of the remaining elements ; Sort the differences in increasing order ; Include the differences while sum remains positive or ; Return the size ; Driver Code ; Function Calling
function findSubset ( a , n ) { let sum = 0 ; let cnt = 0 ; let v = [ ] ; for ( let i = 1 ; i <= n ; i ++ ) { if ( a [ i - 1 ] - i <= 0 ) { sum += a [ i - 1 ] - i ; cnt += 1 ; } else { v . push ( a [ i - 1 ] - i ) ; } } v . sort ( ) ; let ptr = 0 ; while ( ptr < v . length && sum + v [ ptr ] <= 0 ) { cnt += 1 ; ptr += 1 ; sum += v [ ptr ] ; } return cnt ; } let arr = [ 4 , 1 , 6 , 7 , 8 , 2 ] ; let n = arr . length ; document . write ( findSubset ( arr , n ) ) ;