Maximize the profit after selling the tickets | Set 2 ( For elements in range [ 1 , 10 ^ 6 ] ) | Function to find maximum profit after selling K tickets ; Frequency array to store freq of every element of the array ; Modify the arr [ ] so that the array is sorted in O ( N ) ; Variable to store answer ; Traverse the array while K > 0 and j >= 0 ; If arr [ i ] > arr [ j ] then ticket can be brought from counter [ j + 1 , N ] ; If arr [ j ] = = arr [ i ] decrement j until arr [ j ] != arr [ i ] ; Sell tickets from counter [ j + 1 , N ] ; All elements of array are equal Send tickets from each counter 1 time until K > 0. ; Converting answer from long long to let ; Given Input ; Function Call
function maxAmount ( n , k , arr ) { let A = new Array ( 1000001 ) . fill ( 0 ) ; for ( let i = 0 ; i < n ; i ++ ) { A [ arr [ i ] ] ++ ; } let j = 0 ; for ( let i = 0 ; i < 1000001 ; i ++ ) { while ( A [ i ] != 0 ) { arr [ j ++ ] = i ; A [ i ] -- ; } } let ans = 0 ; let mod = 1e9 + 7 ; let i = n - 1 ; j = n - 2 ; while ( k > 0 && j >= 0 ) { if ( arr [ i ] > arr [ j ] ) { ans = ans + Math . min ( k , ( i - j ) ) * arr [ i ] ; k = k - ( i - j ) ; arr [ i ] -- ; } else { while ( j >= 0 && arr [ j ] == arr [ i ] ) j -- ; if ( j < 0 ) break ; ans = ans + Math . min ( k , ( i - j ) ) * arr [ i ] ; k = k - ( i - j ) ; arr [ i ] -- ; } } while ( k > 0 && arr [ i ] != 0 ) { ans = ans + Math . min ( n , k ) * arr [ i ] ; k -= n ; arr [ i ] -- ; } ans = ans % mod ; let x = ans ; return x ; } let n = 5 ; let k = 3 ; let arr = [ 4 , 3 , 6 , 2 , 4 ] ; let ans = maxAmount ( n , k , arr ) ; document . write ( ans ) ;