Order of indices which is lexicographically smallest and sum of elements is <= X | Python3 implementation of the approach ; Function to return the chosen indices ; Maximum indices chosen ; Try to replace the first element in ans by i , making the order lexicographically smaller ; If no further replacement possible return ; If found an index smaller than ind and sum not exceeding X then remove index of smallest value from ans and then add index i to ans ; Driver code ; Print the chosen indices
import sys ; NEW_LINE def solve ( X , A ) : NEW_LINE INDENT minimum = sys . maxsize ; NEW_LINE ind = - 1 ; NEW_LINE for i in range ( len ( A ) ) : NEW_LINE INDENT if ( A [ i ] < minimum ) : NEW_LINE INDENT minimum = A [ i ] ; NEW_LINE ind = i ; NEW_LINE DEDENT DEDENT maxIndChosen = X // minimum ; NEW_LINE ans = [ ] ; NEW_LINE if ( maxIndChosen == 0 ) : NEW_LINE INDENT return ans ; NEW_LINE DEDENT for i in range ( maxIndChosen ) : NEW_LINE INDENT ans . append ( ind ) ; NEW_LINE DEDENT temp = maxIndChosen ; NEW_LINE sum = maxIndChosen * A [ ind ] ; NEW_LINE for i in range ( ind ) : NEW_LINE INDENT if ( sum - X == 0 or temp == 0 ) : NEW_LINE INDENT break ; NEW_LINE DEDENT while ( ( sum - A [ ind ] + A [ i ] ) <= X and temp != 0 ) : NEW_LINE INDENT del ( ans [ 0 ] ) ; NEW_LINE ans . append ( i ) ; NEW_LINE temp -= 1 ; NEW_LINE sum += ( A [ i ] - A [ ind ] ) ; NEW_LINE DEDENT DEDENT ans . sort ( ) ; NEW_LINE return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 5 , 6 , 4 , 8 ] ; NEW_LINE X = 18 ; NEW_LINE ans = solve ( X , A ) ; NEW_LINE for i in range ( len ( ans ) ) : NEW_LINE INDENT print ( ans [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT